太久没看代码了，最近打算复习一下java，又突然想到了排序算法，就把几种常见的排序算法用java敲了一遍，这里统一将无序的序列从小到大排列。
选择排序是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小元素，继续放在下一个位置，直到待排序元素个数为0。
选择排序代码如下：
public void Select_sort(int[] arr) {
int temp,index;
for( int i=0;i<10;i++) {
index = i;
for(int j = i + 1 ; j < 10 ; j++) {
if(arr[j] < arr[index])
index = j;
}
/
temp = arr[i];
arr[i] = arr[index];
arr[index] = temp;
/
swap(arr,i,index);
}
Systemoutprint("经过选择排序后：");
for(int i = 0 ; i < 10 ; i++)
Systemoutprint( arr[i] +" ");
Systemoutprintln("");
}
冒泡排序是一种比较基础的排序算法，其思想是相邻的元素两两比较，较大的元素放后面，较小的元素放前面，这样一次循环下来，最大元素就会归位，若数组中元素个数为n，则经过（n-1）次后，所有元素就依次从小到大排好序了。整个过程如同气泡冒起，因此被称作冒泡排序。
选择排序代码如下：
public void Bubble_sort(int[] arr) {
int temp;
for(int i = 0 ; i < 9 ; i++) {
for(int j = 0 ; j < 10 - i - 1 ;j++) {
if(arr[j] > arr[j+1]) {
/
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
/
swap(arr,j,j+1);
}
}
}
Systemoutprint("经过冒泡排序后：");
for(int i = 0 ; i < 10 ; i++)
Systemoutprint( arr[i] +" ");
Systemoutprintln("");
}
插入排序也是一种常见的排序算法，插入排序的思想是：创建一个与待排序数组等大的数组，每次取出一个待排序数组中的元素，然后将其插入到新数组中合适的位置，使新数组中的元素保持从小到大的顺序。
插入排序代码如下：
public void Insert_sort(int[] arr) {
int length = arrlength;
int[] arr_sort = new int[length];
int count = 0;
for(int i = 0;i < length; i++) {
if(count == 0) {
arr_sort[0] = arr[0];
}else if(arr[i] >= arr_sort[count - 1]) {
arr_sort[count] = arr[i];
}else if(arr[i] < arr_sort[0]) {
insert(arr,arr_sort,arr[i],0,count);
}else {
for(int j = 0;j < count - 1; j++) {
if(arr[i] >= arr_sort[j] && arr[i] < arr_sort[j+1]) {
insert(arr,arr_sort,arr[i],j+1,count);
break;
}
}
}
count++;
}
Systemoutprint("经过插入排序后：");
for(int i = 0 ; i < 10 ; i++)
Systemoutprint( arr_sort[i] +" ");
Systemoutprintln("");
}
public void insert(int[] arr,int[] arr_sort,int value,int index,int count) {
for(int i = count; i > index; i--)
arr_sort[i] = arr_sort[i-1];
arr_sort[index] = value;
}
快速排序的效率比冒泡排序算法有大幅提升。因为使用冒泡排序时，一次外循环只能归位一个值，有n个元素最多就要执行（n-1）次外循环。而使用快速排序时，一次可以将所有元素按大小分成两堆，也就是平均情况下需要logn轮就可以完成排序。
快速排序的思想是：每趟排序时选出一个基准值（这里以首元素为基准值），然后将所有元素与该基准值比较，并按大小分成左右两堆，然后递归执行该过程，直到所有元素都完成排序。
public void Quick_sort(int[] arr, int left, int right) {
if(left >= right)
return ;
int temp,t;
int j = right;
int i = left;
temp = arr[left];
while(i < j) {
while(arr[j] >= temp && i < j)
j--;
while(arr[i] <= temp && i < j)
i++;
if(i < j) {
t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
}
arr[left] = arr[i];
arr[i] = temp;
Quick_sort(arr,left, i - 1);
Quick_sort(arr, i + 1, right);
}
归并排序是建立在归并 *** 作上的一种有效的排序算法，归并排序对序列的元素进行逐层折半分组，然后从最小分组开始比较排序，每两个小分组合并成一个大的分组，逐层进行，最终所有的元素都是有序的。
public void Mergesort(int[] arr,int left,int right) {
if(right - left > 0) {
int[] arr_1 = new int[(right - left)/2 + 1];
int[] arr_2 = new int[(right - left + 1)/2];
int j = 0;
int k = 0;
for(int i = left;i <= right;i++) {
if(i <= (right + left)/2) {
arr_1[j++] = arr[i];
}else {
arr_2[k++] = arr[i];
}
}
Mergesort(arr_1,0,(right - left)/2);
Mergesort(arr_2,0,(right - left - 1)/2);
Merge(arr_1,arr_2,arr);
}
}
public void Merge(int[] arr_1,int[] arr_2,int[] arr) {
int i = 0;
int j = 0;
int k = 0;
int L1 = arr_1length;
int L2 = arr_2length;
while(i < L1 && j < L2) {
if(arr_1[i] <= arr_2[j]) {
arr[k] = arr_1[i];
i++;
}else {
arr[k] = arr_2[j];
j++;
}
k++;
}
if(i == L1) {
for(int t = j;j < L2;j++)
arr[k++] = arr_2[j];
}else {
for(int t = i;i < L1;i++)
arr[k++] = arr_1[i];
}
}
归并排序这里我使用了left，right等变量，使其可以通用，并没有直接用数字表示那么明确，所以给出相关伪代码，便于理解。
Mergesort(arr[0n-1])
//输入：一个可排序数组arr[0n-1]
//输出：非降序排列的数组arr[0n-1]
if n>1
copy arr[0n/2-1] to arr_1[0(n+1)/2-1]//确保arr_1中元素个数>=arr_2中元素个数
//对于总个数为奇数时，arr_1比arr_2中元素多一个；对于总个数为偶数时，没有影响
copy arr[n/2n-1] to arr_2[0n/2-1]
Mergesort(arr_1[0(n+1)/2-1])
Mergesort(arr_2[0n/2-1])
Merge(arr_1,arr_2,arr)
Merge(arr_1[0p-1],arr_2[0q-1],arr[0p+q-1])
//输入：两个有序数组arr_1[0p-1]和arr_2[0q-1]
//输出：将arr_1与arr_2两数组合并到arr
int i<-0;j<-0;k<-0
while i
<p span="" do<="" jif arr_1[i] <= arr_2[j]
arr[k] <- arr_1[i]
i<-i+1
else arr[k] <- arr_2[j];j<-j+1
k<-k+1
if i=p
copy arr_2[jq-1] to arr[kp+q-1]
else copy arr_1[ip-1] to arr[kp+q-1]
package test_1;
import javautilScanner;
public class Test01 {
public static void main(String[] args) {
Scanner sc = new Scanner(Systemin);
int[] arr_1 = new int[10];
for(int i = 0 ; i < 10 ; i++)
arr_1[i] = scnextInt();
Sort demo_1 = new Sort();
//1~5一次只能运行一个，若多个同时运行，则只有第一个有效，后面几个是无效排序。因为第一个运行的已经将带排序数组排好序。
demo_1Select_sort(arr_1);//-----------------------1
//demo_1Bubble_sort(arr_1);//---------------------2
/ //---------------------3
demo_1Quick_sort(arr_1, 0 , arr_1length - 1);
Systemoutprint("经过快速排序后：");
for(int i = 0 ; i < 10 ; i++)
Systemoutprint( arr_1[i] +" ");
Systemoutprintln("");
/
//demo_1Insert_sort(arr_1);//--------------------4
/ //--------------------5
demo_1Mergesort(arr_1,0,arr_1length - 1);
Systemoutprint("经过归并排序后：");
for(int i = 0 ; i < 10 ; i++)
Systemoutprint( arr_1[i] +" ");
Systemoutprintln("");
/
}
}
class Sort {
public void swap(int arr[],int a, int b) {
int t;
t = arr[a];
arr[a] = arr[b];
arr[b] = t;
}
public void Select_sort(int[] arr) {
int temp,index;
for( int i=0;i<10;i++) {
index = i;
for(int j = i + 1 ; j < 10 ; j++) {
if(arr[j] < arr[index])
index = j;
}
/
temp = arr[i];
arr[i] = arr[index];
arr[index] = temp;
/
swap(arr,i,index);
}
Systemoutprint("经过选择排序后：");
for(int i = 0 ; i < 10 ; i++)
Systemoutprint( arr[i] +" ");
Systemoutprintln("");
}
public void Bubble_sort(int[] arr) {
int temp;
for(int i = 0 ; i < 9 ; i++) {
for(int j = 0 ; j < 10 - i - 1 ;j++) {
if(arr[j] > arr[j+1]) {
/
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
/
swap(arr,j,j+1);
}
}
}
Systemoutprint("经过冒泡排序后：");
for(int i = 0 ; i < 10 ; i++)
Systemoutprint( arr[i] +" ");
Systemoutprintln("");
}
public void Quick_sort(int[] arr, int left, int right) {
if(left >= right)
return ;
int temp,t;
int j = right;
int i = left;
temp = arr[left];
while(i < j) {
while(arr[j] >= temp && i < j)
j--;
while(arr[i] <= temp && i < j)
i++;
if(i < j) {
t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
}
arr[left] = arr[i];
arr[i] = temp;
Quick_sort(arr,left, i - 1);
Quick_sort(arr, i + 1, right);
}
public void Insert_sort(int[] arr) {
int length = arrlength;
int[] arr_sort = new int[length];
int count = 0;
for(int i = 0;i < length; i++) {
if(count == 0) {
arr_sort[0] = arr[0];
}else if(arr[i] >= arr_sort[count - 1]) {
arr_sort[count] = arr[i];
}else if(arr[i] < arr_sort[0]) {
insert(arr,arr_sort,arr[i],0,count);
}else {
for(int j = 0;j < count - 1; j++) {
if(arr[i] >= arr_sort[j] && arr[i] < arr_sort[j+1]) {
insert(arr,arr_sort,arr[i],j+1,count);
break;
}
}
}
count++;
}
Systemoutprint("经过插入排序后：");
for(int i = 0 ; i < 10 ; i++)
Systemoutprint( arr_sort[i] +" ");
Systemoutprintln("");
}
public void insert(int[] arr,int[] arr_sort,int value,int index,int count) {
for(int i = count; i > index; i--)
arr_sort[i] = arr_sort[i-1];
arr_sort[index] = value;
}
public void Mergesort(int[] arr,int left,int right) {
if(right - left > 0) {
int[] arr_1 = new int[(right - left)/2 + 1];
int[] arr_2 = new int[(right - left + 1)/2];
int j = 0;
int k = 0;
for(int i = left;i <= right;i++) {
if(i <= (right + left)/2) {
arr_1[j++] = arr[i];
}else {
arr_2[k++] = arr[i];
}
}
Mergesort(arr_1,0,(right - left)/2);
Mergesort(arr_2,0,(right - left - 1)/2);
Merge(arr_1,arr_2,arr);
}
}
public void Merge(int[] arr_1,int[] arr_2,int[] arr) {
int i = 0;
int j = 0;
int k = 0;
int L1 = arr_1length;
int L2 = arr_2length;
while(i < L1 && j < L2) {
if(arr_1[i] <= arr_2[j]) {
arr[k] = arr_1[i];
i++;
}else {
arr[k] = arr_2[j];
j++;
}
k++;
}
if(i == L1) {
for(int t = j;j < L2;j++)
arr[k++] = arr_2[j];
}else {
for(int t = i;i < L1;i++)
arr[k++] = arr_1[i];
}
}
}
若有错误，麻烦指正，不胜感激。
递归是设计和描述算法的一种有力的工具，由于它在复杂算法的描述中被经常采用，为此在进一步介绍其他算法设计方法之前先讨论它。
能采用递归描述的算法通常有这样的特征：为求解规模为N的问题，设法将它分解成规模较小的问题，然后从这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出规模较大问题的解。特别地，当规模N=1时，能直接得解。
递归算法的执行过程分递推和回归两个阶段。在递推阶段，把较复杂的问题（规模为n）的求解推到比原问题简单一些的问题（规模小于n）的求解。例如上例中，求解fib(n)，把它推到求解fib(n-1)和fib(n-2)。也就是说，为计算fib(n)，必须先计算fib(n-1)和fib(n-2)，而计算fib(n-1)和fib(n-2)，又必须先计算fib(n-3)和fib(n-4)。依次类推，直至计算fib(1)和fib(0)，分别能立即得到结果1和0。在递推阶段，必须要有终止递归的情况。例如在函数fib中，当n为1和0的情况。
在回归阶段，当获得最简单情况的解后，逐级返回，依次得到稍复杂问题的解，例如得到fib(1)和fib(0)后，返回得到fib(2)的结果，……，在得到了fib(n-1)和fib(n-2)的结果后，返回得到fib(n)的结果。
在编写递归函数时要注意，函数中的局部变量和参数知识局限于当前调用层，当递推进入“简单问题”层时，原来层次上的参数和局部变量便被隐蔽起来。在一系列“简单问题”层，它们各有自己的参数和局部变量。
由于递归引起一系列的函数调用，并且可能会有一系列的重复计算，递归算法的执行效率相对较低。当某个递归算法能较方便地转换成递推算法时，通常按递推算法编写程序。例如上例计算斐波那契数列的第n项的函数fib(n)应采用递推算法，即从斐波那契数列的前两项出发，逐次由前两项计算出下一项，直至计算出要求的第n项。
选择排序法 是对 定位比较交换法 的一种改进。在讲选择排序法之前我们先来了解一下定位比较交换法。为了便于理解，设有10个数分别存在数组元素a[0]～a[9]中。定位比较交换法是由大到小依次定位a[0]～a[9]中恰当的值（和武林大会中的比武差不多），a[9]中放的自然是最小的数。如定位a[0],先假定a[0]中当前值是最大数，a[0]与后面的元素一一比较，如果a[4]更大，则将a[0]、a[4]交换，a[0]已更新再与后面的a[5]～a[9]比较，如果a[8]还要大，则将a[0]、a[8]交换，a[0]又是新数，再与a[9]比较。一轮比完以后，a[0]就是最大的数了，本次比武的武状元诞生了，接下来从a[1]开始，因为状元要休息了，再来一轮a[1]就是次大的数，也就是榜眼，然后从a[2]开始，比出探花，真成比武大会了，当必到a[8]以后，排序就完成了。
下面给大家一个例子：
mai()
{
int a[10];
int i,j,t;
for ( i = 0; i < 10; i ++ ) scanf("%d",&a[ i ]); /输入10个数，比武报名，报名费用10000￥ ^_^/
for ( i = 0; i < 9; i ++ )
for ( j = i + 1; j < 10; j ++)
if ( a[ i ] < a[ j ] ) { t = a[ i ]; a[ i ] = a[ j ]; a[ j ] = t; } /打不过就要让出头把交椅，不过a[ i ]比较爱面子，不好意思见 a[ j ]，让t帮忙/
for( i = 0; i < 10; i ++) printf("%4d",a[ i ]); /显示排序后的结果/
}
好啦，罗嗦了半天总算把定位比较排序法讲完了，这个方法不错，容易理解，就是有点麻烦，一把椅子换来换去，哎～
所以就有了下面的选择排序法，开始的时候椅子谁也不给，放在一边让大家看着，找个人k记录比赛结果，然后发椅子。具体来讲呢就是，改进定位比较排序法，但是这个改进只是一部分，比较的次数没变，该怎么打还是怎么打，就是不用换椅子了。每次外循环先将定位元素的小标i值记录到K，认为a[k]是最大元素其实i=k还是a[ i ]最大，a[k]与后面的元素一一比较，该交换的也是也不换，就是把K的值改变一下就完了，最后在把a[k]与a[ i ]交换，这样a就是最大的元素了。然后进入下一轮的比较。选择排序法与定位比较排序法相比较，比的次数没变，交换的次数减少了。
下面也写个例子：
main()
{
int a[10];
int i,j,t,k;
for ( i = 0; i < 10; i ++ ) scanf("%d",&a[ i ]); /输入10个数，比武报名，报名费用10000￥ ^_^/
for ( i = 0; i < 9; i ++ )
{ k = i; /裁判AND记者实时追踪报道比赛情况/
for ( j = i + 1; j < 10; j ++)
if ( a[ k ] < a[ j ] ) k = j;
t = a[ i ]; a[ i ] = a[ k ]; a[ k ] = t; / t 发放奖品/
}
for( i = 0; i < 10; i ++) printf("%4d",a[ i ]); /显示排序后的结果/
}
#include <stdioh>
#include <timeh>
#include <stdlibh>
#include <Windowsh>
void shellSort(int a,int len)
{
int step;
int i,j;
int temp;
for(step=len/2; step>0;step/=2)
{
for(i=step;i<len;i++)
{
temp = a[i];
for(j=i-step;(j>=0 && temp < a[j]);j-=step)
{
a[j+step] = a[j];
}
a[j+step] = temp;
}
}
}
void swap(int a,int b)
{
int temp = a;
a = b;
b = temp;
}
void heapify(int a,int n,int k)
{
int l,r,lg = -1;
l = 2k;
r = l+1;
if (l <= n && a[l-1] > a[k-1])
{
lg = l;
}
else
{
lg = k;
}
if (r <= n && a[r-1] > a[lg-1])
{
lg = r;
}
if (lg != k)
{
swap(&a[lg-1],&a[k-1]);
heapify(a,n,lg);
}
}
void build_heap(int a[],int n)
{
for (int i=n/2+1; i>0; i--)
{
heapify(a,n,i);
}
}
void heap_sort(int a[],int n)
{
build_heap(a,n);
for (int i=n; i>0; i--)
{
swap(&a[0],&a[i-1]);
heapify(a,i-1,1);
}
}
int partitions(int a[],long p,long q)
{
long i,j=p-1;
for (i=p; i<q; i++)
{
if (a[i-1] <= a[q-1])
{
j++;
swap(&a[i-1],&a[j-1]);
}
}
j++;
swap(&a[j-1],&a[q-1]);
return j;
}
void quicksort(int a[],long p,long q)
{
long i;
if (p<q)
{
i = partitions(a,p,q);
quicksort(a,p,i-1);
quicksort(a,i+1,q);
}
}
void merge(int a,int start, int mid, int end)
{
int n1 = mid - start + 1;
int n2 = end - mid;
int left = (int )malloc(sizeof(int)n1), right=(int )malloc(sizeof(int)n2);
int i, j, k;
for (i = 0; i < n1; i++) / left holds a[startmid] /
left[i] = a[start+i];
for (j = 0; j < n2; j++) / right holds a[mid+1end] /
right[j] = a[mid+1+j];
i = j = 0;
k = start;
while (i < n1 && j < n2)
if (left[i] < right[j])
a[k++] = left[i++];
else
a[k++] = right[j++];
while (i < n1) / left[] is not exhausted /
a[k++] = left[i++];
while (j < n2) / right[] is not exhausted /
a[k++] = right[j++];
free(left);
free(right);
}
void MergeSort(int a,int start, int end)
{
int mid;
if (start < end)
{
mid = (start + end) / 2;
MergeSort(a,start, mid);
MergeSort(a,mid+1, end);
merge(a,start, mid, end);
}
}
double gettime(LARGE_INTEGER t,LARGE_INTEGER t1,LARGE_INTEGER t2)
{
double time;
if (tLowPart==0 && tHighPart==0)
time = -1;
else
{
time = (float)(t2LowPart - t1LowPart);
if (time < 0) time += 2^32;
time /= (tLowPart+tHighPart 2^32);
}
return time;
}
int main()
{
const int NUM = 1000;
srand(time(NULL));
int data[NUM];
int i;
for (i=0; i<NUM; ++i)
{
data[i] = rand()/(RAND_MAX/20000+1);
}
LARGE_INTEGER t,t1,t2;
QueryPerformanceFrequency(&t);
QueryPerformanceFrequency(&t1);
shellSort(data,NUM);
QueryPerformanceFrequency(&t2);
printf("shell time:%04f\n",gettime(t,t1,t2));
QueryPerformanceFrequency(&t1);
heap_sort(data,NUM);
QueryPerformanceFrequency(&t2);
printf("shell time:%04f\n",gettime(t,t1,t2));
QueryPerformanceFrequency(&t1);
quicksort(data,1,NUM);
QueryPerformanceFrequency(&t2);
printf("shell time:%04f\n",gettime(t,t1,t2));
QueryPerformanceFrequency(&t1);
MergeSort(data,0,NUM);
QueryPerformanceFrequency(&t2);
printf("shell time:%04f\n",gettime(t,t1,t2));
return 0;
}
一、递归算法基本思路：
Java递归算法是基于Java语言实现的递归算法。递归算法是一种直接或者间接调用自身函数或者方法的算法。递归算法实质是把问题分解成规模缩小的同类问题的子问题，然后递归调用方法表示问题的解。递归往往能给我们带来非常简洁非常直观的代码形式，从而使我们的编码大大简化，然而递归的思维确实跟我们的常规思维相逆的，通常都是从上而下的思维问题，而递归趋势从下往上的进行思维。
二、递归算法解决问题的特点：
1递归就是方法里调用自身。
2在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。
3递归算法代码显得很简洁，但递归算法解题的运行效率较低。所以不提倡用递归设计程序。
4在递归调用的过程中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等，所以一般不提倡用递归算法设计程序。
5在做递归算法的时候，一定把握出口，也就是做递归算法必须要有一个明确的递归结束条件。这一点是非常重要的。其实这个出口就是一个条件，当满足了这个条件的时候我们就不再递归了。
三、代码示例：
public class Factorial {//this is a recursive function
int fact(int n){
if (n==1) return 1;
return fact(n-1)n;
}
} public class TestFactorial {
public static void main(String[] args) {
// TODO Auto-generated method stub
Factorial factorial=new Factorial();
Systemoutprintln("factorial(5)="+factorialfact(5));
}
}
代码执行流程图如下：
此程序中n=5就是程序的出口。
快速排序中，首先要进行一次划分以确定轴值（即序列中在它右边都大于它，左边的都小于它）的位置，快速排序中其实就是不停的对序列划分比如：序列 23 13 49 6 31 19 28进行一次划分（即用一个函数实现）后 19 13 6 23 31 49 28此时23为轴值，然后对括号中的俩子序列分别进行快速排序！（既递归，调用自身函数）。
1 判定序列array[m，n]长度是否为1，如果为1直接返回
2 否则分别归并排序序列array[m, (m + n) / 2]和序列array[(m + n) / 2 + 1, n]
3 归并序列array[m, n]
void merge(int array[], int begin, int end)
{
if ((end - begin) <= 1)
return;
merge(array, begin, (begin + end) / 2);
merge(array, (begin + end) / 2 + 1, end);
//合并两个数组区域。这部份就不写了，一个序列2元素顺序插入序列1的过程
}
以上就是关于常见的排序算法—选择，冒泡，插入，快速，归并全部的内容，包括:常见的排序算法—选择，冒泡，插入，快速，归并、计算机算法中的递归法与选择排序法是什么请细讲、C语言课程设计：shell排序、堆排序、快速排序、归并(递归和非递归)排序5种算法效率分析！求能运行的源码！等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）