排序分类
1）稳定/不稳定排序：假设在待排序的文件中，存在两个或两个以上的记录具有相同的关键字，在用某种排序法排序后，若这些相同关键字的元素的相对次序仍然不变，则这种排序方法是稳定的。
稳定排序： 冒泡，插入，基数，归
并，二分法插入
不稳定排序： 选择，快速，希尔，堆
2）内排序/外排序：在排序过程中，全部记录存放在内存，则称为内排序，如果排序过程中需要使用外存，则称为外排序。
内排序有可以分为以下几类： (1)、插入排序：直接插入排序、二分法插入排序、希尔排序。 (2)、选择排序：简单选择排序、堆排序。 (3)、交换排序：冒泡排序、快速排序。 (4)、归并排序 (5)、基数排序
排序性能
一、插入排序
•思想：每步将一个待排序的记录，按其顺序码大小插入到前面已经排序的字序列的合适位置，直到全部插入排序完为止。
•关键问题：在前面已经排好序的序列中找到合适的插入位置。
•方法：
–直接插入排序
–二分插入排序
–希尔排序
（1）直接插入排序
1、基本思想：每步将一个待排序的记录，按其顺序码大小插入到前面已经排序的字序列的合适位置（从后向前找到合适位置后），直到全部插入排序完为止。
2、基本过程：
第一趟比较前两个数，然后把第二个数按大小插入到有序表中； 第二趟把第三个数据与前两个数从前向后扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。
直接插入排序属于稳定的排序，最坏时间复杂性为O(n^2)，空间复杂度为O(1)。
直接插入排序是由两层嵌套循环组成的。外层循环标识并决定待比较的数值。内层循环为待比较数值确定其最终位置。直接插入排序是将待比较的数值与它的前一个数值进行比较，所以外层循环是从第二个数值开始的。当前一数值比待比较数值大的情况下继续循环比较，直到找到比待比较数值小的并将待比较数值置入其后一位置，结束该次循环。
值得注意的是，我们必需用一个存储空间来保存当前待比较的数值，因为当一趟比较完成时，我们要将待比较数值置入比它小的数值的后一位。
3、实例
4、代码实现
4.1 代码实现1
/// <summary> /// 直接插入排序 /// </summary> /// <param name="arry">要排序的数组</param> public static void InsertSort(this int[] arry) { //直接插入排序是将待比较的数值与它的前一个数值进行比较，所以外层循环是从第二个数值开始的 for (int i = 1; i < arry.Length; i++) { //如果当前元素小于其前面的元素 if (arry[i] < arry[i - 1]) { //用一个变量来保存当前待比较的数值，因为当一趟比较完成时，我们要将待比较数值置入比它小的数值的后一位 int temp = arry[i]; int j = 0; for (j = i - 1; j >= 0 && temp < arry[j]; j--) { arry[j + 1] = arry[j]; } arry[j + 1] = temp; } } }
测试
static void Main(string[] args) { int[] arry = new int[] { 34,1,221,50,44,58,12}; //arry.BubbleSort(); //arry.QuickSort(0, arry.Length-1 ); arry.InsertSort(); for (int i = 0; i < arry.Length; i++) { Console.Write(" " + arry[i]); } Console.Read(); }
4.2 代码实现2
/*insert the next element into the sorted part*/ void insert_sort(int a[], int ac) { /*use swap*/ int i,j; for (j=1; j < ac; j++) { i = j-1; while((i>=0) && (a[i+1] < a[i])) { swap(a+i+1, a+i); i--; } } }
4.3 代码实现3
package com.sort; public class 直接插入排序 { public static void main(String[] args) { int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1}; System.out.println("排序之前："); for (int i = 0; i < a.length; i++) { System.out.print(a[i]+" "); } //直接插入排序 for (int i = 1; i < a.length; i++) { //待插入元素 int temp = a[i]; int j; /*for (j = i-1; j>=0 && a[j]>temp; j--) { //将大于temp的往后移动一位 a[j+1] = a[j]; }*/ for (j = i-1; j>=0; j--) { //将大于temp的往后移动一位 if(a[j]>temp){ a[j+1] = a[j]; }else{ break; } } a[j+1] = temp; } System.out.println(); System.out.println("排序之后："); for (int i = 0; i < a.length; i++) { System.out.print(a[i]+" "); } } }
4.4 java
public class Test{ public static void insertSort(int[] source){ for (int i=0; i<source.length; i++){ for(int j=i; (j>0)&&(source[j]<source[j-1]);j--){ swap(source,j,j-1); } } } private static void swap (int [] source, int x,int y){ int temp=source[x]; source[x]=source[y]; source[y]=temp; } public static void main(String[] args){ int [] a={4,2,1,6,3,6,0,-5,1,1}; int i; insertSort(a); for(i=0;i<10;i++){ System.out.printf("%d ",a[i]); } } }
（2）二分法插入排序
1、基本思想：
二分法插入排序的思想和直接插入一样，只是找合适的插入位置的方式不同，这里是按二分法找到合适的位置，可以减少比较的次数。在插入第i个元素时，对前面的0～i-1元素进行折半，先跟他们 中间的那个元素比，如果小，则对前半再进行折半，否则对后半 进行折半，直到left>right，然后再把第i个元素前1位与目标位置之间 的所有元素后移，再把第i个元素放在目标位置上。
二分法插入排序也是稳定的。
二分插入排序的比较次数与待排序记录的初始状态无关，仅依赖于记录的个数。当n较大时，比直接插入排序的最大比较次数少得多。但大于直接插入排序的最小比较次数。算法的移动次数与直接插入排序算法的相同，最坏的情况为n2/2，最好的情况为n，平均移动次数为O(n2)。
2、实例
3、代码实现
3.1 代码1
package com.sort; public class DichotomySort { public static void main(String[] args) { int[] a={49,38,65,97,176,213,227,49,78,34,12,164,11,18,1}; System.out.println("排序之前："); for (int i = 0; i < a.length; i++) { System.out.print(a[i]+" "); } //二分插入排序 sort(a); System.out.println(); System.out.println("排序之后："); for (int i = 0; i < a.length; i++) { System.out.print(a[i]+" "); } } private static void sort(int[] a) { for (int i = 0; i < a.length; i++) { int temp = a[i]; int left = 0; int right = i-1; int mid = 0; while(left<=right){ mid = (left+right)/2; if(temp<a[mid]){ right = mid-1; }else{ left = mid+1; } } for (int j = i-1; j >= left; j--) { a[j+1] = a[j]; } if(left != i){ a[left] = temp; } } } }
（3）希尔排序
1、基本思想：
先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法。
Shell Sorting依赖于间隔(step)的选取。一个常见的选择是将本次间隔设置为上次间隔的1/1.3。
我们知道一次插入排序是稳定的，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以希尔排序是不稳定的。希尔排序的时间性能优于直接插入排序，原因如下：
（1）当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。
（2）当n值较小时，n和n2的差别也较小，即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度0(n2)差别不大。
（3）在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量di逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按di-1作为距离排过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。
因此，希尔排序在效率上较直接插人排序有较大的改进。
希尔排序的平均时间复杂度为O(nlogn)？。
2、实例
3、代码实现
3.1 代码1
/*quickly sort the turtles at the tail of the array*/ void shell_sort(int a[], int ac) { int step; int i,j; int nsub; int *sub; /* initialize step */ step = 1; while(step < ac) step = 3*step + 1; /* when step becomes 1, it's equivalent to the bubble sort*/ while(step > 1) { /* step will go down to 1 at most */ step = step/3 + 1; for(i=0; i<step; i++) { /* pick an element every step, and combine into a sub-array */ nsub = (ac - i - 1)/step + 1; sub = (int *) malloc(sizeof(int)*nsub); for(j=0; j<nsub; j++) { sub[j] = a[i+j*step]; } /* sort the sub-array by bubble sorting. It could be other sorting methods */ bubble_sort(sub, nsub); /* put back the sub-array*/ for(j=0; j<nsub; j++) { a[i+j*step] = sub[j]; } /* free sub-array */ free(sub); } } }
3.2 代码2
package com.sort; //不稳定 public class 希尔排序 { public static void main(String[] args) { int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1}; System.out.println("排序之前："); for (int i = 0; i < a.length; i++) { System.out.print(a[i]+" "); } //希尔排序 int d = a.length; while(true){ d = d / 2; for(int x=0;x<d;x++){ for(int i=x+d;i<a.length;i=i+d){ int temp = a[i]; int j; for(j=i-d;j>=0&&a[j]>temp;j=j-d){ a[j+d] = a[j]; } a[j+d] = temp; } } if(d == 1){ break; } } System.out.println(); System.out.println("排序之后："); for (int i = 0; i < a.length; i++) { System.out.print(a[i]+" "); } } }
二、选择排序
•思想：每趟从待排序的记录序列中选择关键字最小的记录放置到已排序表的最前位置，直到全部排完。
•关键问题：在剩余的待排序记录序列中找到最小关键码记录。
•方法：
–直接选择排序
–堆排序
（1）简单的选择排序
1、基本思想：
在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。
在简单选择排序过程中，所需移动记录的次数比较少。最好情况下，即待排序记录初始状态就已经是正序排列了，则不需要移动记录。最坏情况下，即待排序记录初始状态是按逆序排列的，则需要移动记录的次数最多为3（n-1）。简单选择排序过程中需要进行的比较次数与初始状态下待排序的记录序列的排列情况无关。当i=1时，需进行n-1次比较；当i=2时，需进行n-2次比较；依次类推，共需要进行的比较次数是(n-1)+(n-2)+…+2+1=n(n-1)/2，即进行比较操作的时间复杂度为O(n^2)，进行移动操作的时间复杂度为O(n)。
2、实例
3、代码实现
3.1 代码1
package com.sort; //不稳定 public class 简单的选择排序 { public static void main(String[] args) { int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1,8}; System.out.println("排序之前："); for (int i = 0; i < a.length; i++) { System.out.print(a[i]+" "); } //简单的选择排序 for (int i = 0; i < a.length; i++) { int min = a[i]; int n=i; //最小数的索引 for(int j=i+1;j<a.length;j++){ if(a[j]<min){ //找出最小的数 min = a[j]; n = j; } } a[n] = a[i]; a[i] = min; } System.out.println(); System.out.println("排序之后："); for (int i = 0; i < a.length; i++) { System.out.print(a[i]+" "); } } }
3.2代码2
/// <summary> /// 简单选择排序 /// </summary> /// <param name="arry">待排序的数组</param> public static void SimpleSelectSort(this int[] arry) { int tmp = 0; int t = 0;//最小数标记 for (int i = 0; i < arry.Length; i++) { t = i; for (int j = i + 1; j < arry.Length; j++) { if (arry[t] > arry[j]) { t = j; } } tmp = arry[i]; arry[i] = arry[t]; arry[t] = tmp; } }
static void Main(string[] args) { int[] arry = new int[] { 34,1,221,50,44,58,12}; //arry.BubbleSort(); //arry.QuickSort(0, arry.Length-1 ); //arry.InsertSort(); //arry.ShellSort(); arry.SimpleSelectSort(); for (int i = 0; i < arry.Length; i++) { Console.Write(" " + arry[i]); } Console.Read(); }
3.3 java
public class Test{ public static void selectSort(int[] source){ for (int i=0; i<source.length; i++){ for(int j=i+1;j<source.length;j++){ if(source[i]>source[j]){ swap(source,i,j); } } } } private static void swap (int [] source, int x,int y){ int temp=source[x]; source[x]=source[y]; source[y]=temp; } public static void main(String[] args){ int [] a={4,2,1,6,3,6,0,-5,1,1}; int i; selectSort(a); for(i=0;i<10;i++){ System.out.printf("%d ",a[i]); } } }
（2）堆排序
1、基本思想：
堆排序是一种树形选择排序，是对直接选择排序的有效改进。
堆的定义下：具有n个元素的序列 （h1,h2,...,hn),当且仅当满足（hi>=h2i,hi>=2i+1）或（hi<=h2i,hi<=2i+1） (i=1,2,...,n/2)时称之为堆。在这里只讨论满足前者条件的堆。由堆的定义可以看出，堆顶元素（即第一个元素）必为最大项（大顶堆）。完全二 叉树可以很直观地表示堆的结构。堆顶为根，其它为左子树、右子树。
这里的堆(二叉堆),指得不是堆栈的那个堆,而是一种数据结构。堆可以视为一棵完全的二叉树,完全二叉树的一个“优秀”的性质是,除了最底层之外,每一层都是满的,这使得堆可以利用数组来表示,每一个结点对应数组中的一个元素.
堆排序也是一种不稳定的排序算法。
堆排序优于简单选择排序的原因： 直接选择排序中，为了从R[1..n]中选出关键字最小的记录，必须进行n-1次比较，然后在R[2..n]中选出关键字最小的记录，又需要做n-2次比较。事实上，后面的n-2次比较中，有许多比较可能在前面的n-1次比较中已经做过，但由于前一趟排序时未保留这些比较结果，所以后一趟排序时又重复执行了这些比较操作。
堆排序可通过树形结构保存部分比较结果，可减少比较次数。
堆排序的最坏时间复杂度为O(nlogn)。堆序的平均性能较接近于最坏性能。由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。
数组与堆：
最大堆：
堆中每个父节点的元素值都大于等于其孩子结点（如果存在）,这样的堆就是一个最大堆。因此,最大堆中的最大元素值出现在根结点(堆顶)
建立最大堆：
2、实例
堆排序就是把堆顶的最大数取出，将剩余的堆继续调整为最大堆，以递归实现；剩余部分调整为最大堆后,再次将堆顶的最大数取出,再将剩余部分调整为最大堆,这个过程持续到剩余数只有一个时结束
1）
2)
3)
3. 代码实现
3.1 代码1
package com.sort; //不稳定 import java.util.Arrays; public class HeapSort { public static void main(String[] args) { int[] a={49,38,65,97,76,13,27,49,78,34,12,64}; int arrayLength=a.length; //循环建堆 for(int i=0;i<arrayLength-1;i++){ //建堆 buildMaxHeap(a,arrayLength-1-i); //交换堆顶和最后一个元素 swap(a,0,arrayLength-1-i); System.out.println(Arrays.toString(a)); } } //对data数组从0到lastIndex建大顶堆 public static void buildMaxHeap(int[] data, int lastIndex){ //从lastIndex处节点（最后一个节点）的父节点开始 for(int i=(lastIndex-1)/2;i>=0;i--){ //k保存正在判断的节点 int k=i; //如果当前k节点的子节点存在 while(k*2+1<=lastIndex){ //k节点的左子节点的索引 int biggerIndex=2*k+1; //如果biggerIndex小于lastIndex，即biggerIndex+1代表的k节点的右子节点存在 if(biggerIndex<lastIndex){ //若果右子节点的值较大 if(data[biggerIndex]<data[biggerIndex+1]){ //biggerIndex总是记录较大子节点的索引 biggerIndex++; } } //如果k节点的值小于其较大的子节点的值 if(data[k]<data[biggerIndex]){ //交换他们 swap(data,k,biggerIndex); //将biggerIndex赋予k，开始while循环的下一次循环，重新保证k节点的值大于其左右子节点的值 k=biggerIndex; }else{ break; } } } } //交换 private static void swap(int[] data, int i, int j) { int tmp=data[i]; data[i]=data[j]; data[j]=tmp; } }
3.2 代码2
/// <summary> /// 堆排序 /// </summary> /// <param name="arry"></param> public static void HeapSort(this int[] arry, int top) { List<int> topNode = new List<int>(); for (int i = arry.Length / 2 - 1; i >= 0; i--) { HeapAdjust(arry, i, arry.Length); } for (int i = arry.Length - 1; i >= arry.Length - top; i--) { int temp = arry[0]; arry[0] = arry[i]; arry[i] = temp; HeapAdjust(arry, 0, i); } } /// <summary> /// 构建堆 /// </summary> /// <param name="arry"></param> /// <param name="parent"></param> /// <param name="length"></param> private static void HeapAdjust(int[] arry, int parent, int length) { int temp = arry[parent]; int child = 2 * parent + 1; while (child < length) { if (child + 1 < length && arry[child] < arry[child + 1]) child++; if (temp >= arry[child]) break; arry[parent] = arry[child]; parent = child; child = 2 * parent + 1; } arry[parent] = temp; }
static void Main(string[] args) { int[] arry = new int[] { 34,1,221,50,44,58,12}; //arry.BubbleSort(); //arry.QuickSort(0, arry.Length-1 ); //arry.InsertSort(); //arry.ShellSort(); //arry.SimpleSelectSort(); arry.HeapSort(arry.Length); for (int i = 0; i < arry.Length; i++) { Console.Write(" " + arry[i]); } Console.Read(); }
三、交换排序
（1）冒泡排序
1、基本思想：
在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。
冒泡排序是一种稳定的排序方法。
•若文件初状为正序，则一趟起泡就可完成排序，排序码的比较次数为n-1，且没有记录移动，时间复杂度是O(n)
•若文件初态为逆序，则需要n-1趟起泡，每趟进行n-i次排序码的比较，且每次比较都移动三次，比较和移动次数均达到最大值∶O(n2)
•起泡排序平均时间复杂度为O(n2)
2、实例
3.代码
3.1代码1
package com.sort; //稳定 public class 冒泡排序 { public static void main(String[] args) { int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1,8}; System.out.println("排序之前："); for (int i = 0; i < a.length; i++) { System.out.print(a[i]+" "); } //冒泡排序 for (int i = 0; i < a.length; i++) { for(int j = 0; j<a.length-i-1; j++){ //这里-i主要是每遍历一次都把最大的i个数沉到最底下去了，没有必要再替换了 if(a[j]>a[j+1]){ int temp = a[j]; a[j] = a[j+1]; a[j+1] = temp; } } } System.out.println(); System.out.println("排序之后："); for (int i = 0; i < a.length; i++) { System.out.print(a[i]+" "); } } }
class Program { static void Main(string[] args) { int[] arry = new int[] { 1, 2, 3, 4, 1, -1 }; arry.BubbleSort(); for (int i = 0; i < arry.Length; i++) { Console.Write(" " + arry[i]); } Console.Read(); } }
3.2 代码2
/// <summary> /// 冒泡排序 /// </summary> /// <param name="arry">要排序的整数数组</param> public static void BubbleSort(this int[] arry) { for (int i = 0; i < arry.Length-1; i++) { for (int j = 0; j < arry.Length - 1 - i; j++) { //比较相邻的两个元素，如果前面的比后面的大，则交换位置 if (arry[j] > arry[j + 1]) { int temp = arry[j + 1]; arry[j + 1] = arry[j]; arry[j] = temp; } } } }
3.3 java
public class Test{ public static void bubbleSort(int[] source){ for (int i=source.length-1; i>0; i--){ for(int j=0;j<i;j++){ if(source[j]>source[j+1]){ swap(source,j,j+1); } } } } private static void swap (int [] source, int x,int y){ int temp=source[x]; source[x]=source[y]; source[y]=temp; } public static void main(String[] args){ int [] a={4,2,1,6,3,6,0,-5,1,1}; int i; bubbleSort(a); for(i=0;i<10;i++){ System.out.printf("%d ",a[i]); } } }
改进：增加exchange 交换标志，若为TRUE则交换完成
void bubbleSort(Seqlist R){ int i,j; Boolean exchange; for(int i=1; i<n; i++){ exchange=False; for(j=n-1;j>=i;j--) if(R[j+1].key<R[j].key){ R[0]=R[j+1]; R[j+1]=R[j]; R[j]=R[0]; exchange=TRUE; } if(!exchange) return; } }
（2）快速排序
1、基本思想：
选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描，将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。
一趟快速排序的算法是：
1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；
2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]；
3）从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]和A[i]互换；
4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]互换；
5）重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。
1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；
2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]；
3）从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]和A[i]互换；
4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]互换；
5）重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。
2、实例
3、代码实现
3.1 代码1
package com.sort; //不稳定 public class 快速排序 { public static void main(String[] args) { int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1,8}; System.out.println("排序之前："); for (int i = 0; i < a.length; i++) { System.out.print(a[i]+" "); } //快速排序 quick(a); System.out.println(); System.out.println("排序之后："); for (int i = 0; i < a.length; i++) { System.out.print(a[i]+" "); } } private static void quick(int[] a) { if(a.length>0){ quickSort(a,0,a.length-1); } } private static void quickSort(int[] a, int low, int high) { if(low<high){ //如果不加这个判断递归会无法退出导致堆栈溢出异常 int middle = getMiddle(a,low,high); quickSort(a, 0, middle-1); quickSort(a, middle+1, high); } } private static int getMiddle(int[] a, int low, int high) { int temp = a[low];//基准元素 while(low<high){ //找到比基准元素小的元素位置 while(low<high && a[high]>=temp){ high--; } a[low] = a[high]; while(low<high && a[low]<=temp){ low++; } a[high] = a[low]; } a[low] = temp; return low; } }
3.2 代码2
//快速排序的元素移动 int fastSort(int arr[], int left, int right){ int center = (left+right)/2; int num = arr[center]; //记录中枢点的位置，这里选择最左边点当做中枢点 while(left < right){ //比枢纽小的移动到左边 while(left < right && arr[right] >= num){ right--; //一直到有一个元素小于所选关键中枢为止 } arr[left] = arr[right]; while(left < right && arr[left] <= num){ left++; //一直到有一个元素大于所选关键中枢为止 } arr[right] = arr[left]; //关键字入列 } arr[left] = num; return left; } //快速排序递归划分 int fastSortSelf(int arr[], int left, int right){ if(left < right){ int lowLocation = fastSort(arr,left,right); //第一个指针的位置 fastSortSelf(arr,left,lowLocation - 1); fastSortSelf(arr,lowLocation + 1,right); } } //快速排序 void fast(int arr[], int n){ fastSortSelf(arr,0,n-1); //记录时间 }
3.3 代码3
/// <summary> /// 快速排序 /// </summary> /// <param name="arry">要排序的数组</param> /// <param name="left">低位</param> /// <param name="right">高位</param> public static void QuickSort(this int[] arry, int left, int right) { //左边索引小于右边，则还未排序完成 if (left < right) { //取中间的元素作为比较基准，小于他的往左边移，大于他的往右边移 int middle = arry[(left + right) / 2]; int i = left - 1; int j = right + 1; while (true) { //移动下标，左边的往右移动，右边的向左移动 while (arry[++i] < middle && i < right); while (arry[--j] > middle && j > 0); if (i >= j) break; //交换位置 int number = arry[i]; arry[i] = arry[j]; arry[j] = number; } QuickSort(arry, left, i - 1); QuickSort(arry, j + 1, right); } }
static void Main(string[] args) { int[] arry = new int[] { 34,1,221,50,44,58,12,1,1}; //arry.BubbleSort(); arry.QuickSort(0, arry.Length-1 ); for (int i = 0; i < arry.Length; i++) { Console.Write(" " + arry[i]); } Console.Read(); }
四、归并排序
1、基本思想:
归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。将有 n个对象的原始序 列看作 n个有序子列，每个序列的长度为1，从第一个子序列开始，把相邻的子序列两两合并得到[n/2]个长度为2或者是1的归并项，（如果n为奇数，则最后一个有序子序列的长度为1），称这一个过程为一趟归并排序。然后重复上述过程指导得到一个长度为n的序列为止。
2、实例
3、代码实现
3.1 代码1
/// <summary> /// 归并排序 /// </summary> /// <param name="arry"></param> /// <param name="first"></param> /// <param name="last"></param> public static void MergeSort(this int[] arry, int first, int last) { if (first + 1 < last) { int mid = (first + last) / 2; MergeSort(arry, first, mid); MergeSort(arry, mid, last); Merger(arry, first, mid, last); } } /// <summary> /// 归并 /// </summary> /// <param name="arry"></param> /// <param name="first"></param> /// <param name="mid"></param> /// <param name="last"></param> private static void Merger(int[] arry, int first, int mid, int last) { Queue<int> tempV = new Queue<int>(); int indexA, indexB; //设置indexA，并扫描subArray1 [first,mid] //设置indexB,并扫描subArray2 [mid,last] indexA = first; indexB = mid; //在没有比较完两个子标的情况下，比较 v[indexA]和v[indexB] //将其中小的放到临时变量tempV中 while (indexA < mid && indexB < last) { if (arry[indexA] < arry[indexB]) { tempV.Enqueue(arry[indexA]); indexA++; } else { tempV.Enqueue(arry[indexB]); indexB++; } } //复制没有比较完子表中的元素 while (indexA < mid) { tempV.Enqueue(arry[indexA]); indexA++; } while (indexB < last) { tempV.Enqueue(arry[indexB]); indexB++; } int index = 0; while (tempV.Count > 0) { arry[first + index] = tempV.Dequeue(); index++; } }
static void Main(string[] args) { int[] arry = new int[] { 34,1,221,50,44,58,12}; //arry.BubbleSort(); //arry.QuickSort(0, arry.Length-1 ); //arry.InsertSort(); //arry.ShellSort(); //arry.SimpleSelectSort(); //arry.HeapSort(arry.Length); arry.MergeSort(0, arry.Length); for (int i = 0; i < arry.Length; i++) { Console.Write(" " + arry[i]); } Console.Read(); }
3.2 代码2
package com.sort; //稳定 public class 归并排序 { public static void main(String[] args) { int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1,8}; System.out.println("排序之前："); for (int i = 0; i < a.length; i++) { System.out.print(a[i]+" "); } //归并排序 mergeSort(a,0,a.length-1); System.out.println(); System.out.println("排序之后："); for (int i = 0; i < a.length; i++) { System.out.print(a[i]+" "); } } private static void mergeSort(int[] a, int left, int right) { if(left<right){ int middle = (left+right)/2; //对左边进行递归 mergeSort(a, left, middle); //对右边进行递归 mergeSort(a, middle+1, right); //合并 merge(a,left,middle,right); } } private static void merge(int[] a, int left, int middle, int right) { int[] tmpArr = new int[a.length]; int mid = middle+1; //右边的起始位置 int tmp = left; int third = left; while(left<=middle && mid<=right){ //从两个数组中选取较小的数放入中间数组 if(a[left]<=a[mid]){ tmpArr[third++] = a[left++]; }else{ tmpArr[third++] = a[mid++]; } } //将剩余的部分放入中间数组 while(left<=middle){ tmpArr[third++] = a[left++]; } while(mid<=right){ tmpArr[third++] = a[mid++]; } //将中间数组复制回原数组 while(tmp<=right){ a[tmp] = tmpArr[tmp++]; } } }
五、基数排序
1、基本思想：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。
2、实例
3、代码实现
3.1 代码1
/// <summary> /// 基数排序 /// 约定:待排数字中没有0,如果某桶内数字为0则表示该桶未被使用,输出时跳过即可 /// </summary> /// <param name="arry">待排数组</param> /// <param name="array_x">桶数组第一维长度</param> /// <param name="array_y">桶数组第二维长度</param> public static void RadixSort(this int[] arry, int array_x = 10, int array_y = 100) { /* 最大数字不超过999999999...(array_x个9) */ for (int i = 0; i < array_x; i++) { int[,] bucket = new int[array_x, array_y]; foreach (var item in arry) { int temp = (item / (int)Math.Pow(10, i)) % 10; for (int l = 0; l < array_y; l++) { if (bucket[temp, l] == 0) { bucket[temp, l] = item; break; } } } for (int o = 0, x = 0; x < array_x; x++) { for (int y = 0; y < array_y; y++) { if (bucket[x, y] == 0) continue; arry[o++] = bucket[x, y]; } } } }
static void Main(string[] args) { int[] arry = new int[] { 34,1,221,50,44,58,12}; //arry.BubbleSort(); //arry.QuickSort(0, arry.Length-1 ); //arry.InsertSort(); //arry.ShellSort(); //arry.SimpleSelectSort(); //arry.HeapSort(arry.Length); //arry.MergeSort(0, arry.Length); arry.RadixSort(); for (int i = 0; i < arry.Length; i++) { Console.Write(" " + arry[i]); } Console.Read(); }
3.2 代码2
package com.sort; import java.util.ArrayList; import java.util.List; //稳定 public class 基数排序 { public static void main(String[] args) { int[] a={49,38,65,97,176,213,227,49,78,34,12,164,11,18,1}; System.out.println("排序之前："); for (int i = 0; i < a.length; i++) { System.out.print(a[i]+" "); } //基数排序 sort(a); System.out.println(); System.out.println("排序之后："); for (int i = 0; i < a.length; i++) { System.out.print(a[i]+" "); } } private static void sort(int[] array) { //找到最大数，确定要排序几趟 int max = 0; for (int i = 0; i < array.length; i++) { if(max<array[i]){ max = array[i]; } } //判断位数 int times = 0; while(max>0){ max = max/10; times++; } //建立十个队列 List<ArrayList> queue = new ArrayList<ArrayList>(); for (int i = 0; i < 10; i++) { ArrayList queue1 = new ArrayList(); queue.add(queue1); } //进行times次分配和收集 for (int i = 0; i < times; i++) { //分配 for (int j = 0; j < array.length; j++) { int x = array[j]%(int)Math.pow(10, i+1)/(int)Math.pow(10, i); ArrayList queue2 = queue.get(x); queue2.add(array[j]); queue.set(x,queue2); } //收集 int count = 0; for (int j = 0; j < 10; j++) { while(queue.get(j).size()>0){ ArrayList<Integer> queue3 = queue.get(j); array[count] = queue3.get(0); queue3.remove(0); count++; } } } } }
各种算法比较
#include <iostream> #include <iomanip> #include <stdlib.h> #include <time.h> using namespace std; clock_t start_time, end_time; int times; void printfArr(int arr[], int n){ for(int i = 0; i < n; i++){ cout<<arr[i]<<" "; } } //冒泡排序 void bubbling(int arr[], int n){ start_time = clock(); int i, j, temp; for (j = 0; j < n - 1; j++){ for (i = 0; i < n - 1 - j; i++){ if(arr[i] > arr[i + 1]){ temp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = temp; } } } end_time = clock(); times = static_cast<double>(end_time-start_time)/CLOCKS_PER_SEC*1000; cout <<right ; cout <<setw(7) <<times<<"ms"; } //直接选择排序 void directDialing(int arr[], int n){ start_time = clock(); int i,j,k,num; for(i = 0; i < n; i++){ num = 0; for(j = 0; j < n-i; j++){ if(arr[j] > arr[num]){ num = j; } } k = arr[n-i-1]; arr[n-i-1] = arr[num]; arr[num] = k; } end_time = clock(); times = static_cast<double>(end_time-start_time)/CLOCKS_PER_SEC*1000; cout <<right ; cout <<setw(7) <<times<<"ms"; } //直接插入排序 (On2) void insert(int arr[], int n){ start_time = clock(); int m,i,k; for(i = 1; i < n; i++){ m = arr[i]; for(k = i-1; k >= 0; k--){ if(arr[k] > m){ arr[k+1] = arr[k]; }else{ break; } } arr[k+1] = m; } end_time = clock(); times = static_cast<double>(end_time-start_time)/CLOCKS_PER_SEC*1000; cout <<right ; cout <<setw(7) <<times<<"ms"; } //希尔排序 void Heer(int arr[], int n){ start_time = clock(); int i,j,k,num; k = n/2; while(k > 0){ for(i = k; i < n; i++){ num = arr[i]; for(j = i - k;j >= 0; j -= k){ if(arr[j] > num){ arr[j+k] = arr[j]; }else{ break; } } arr[j+k] = num; } k = k/2; } end_time = clock(); times = static_cast<double>(end_time-start_time)/CLOCKS_PER_SEC*1000; cout <<right ; cout <<setw(7) <<times<<"ms"; } //堆调整 void adjust(int arr[], int n, int length){ int max,b; while(n * 2 +1 <= length){//说明存在左节点 max = n * 2 + 1; if(n * 2 + 2 <= length){//说明存在右节点 if(arr[max] < arr[n * 2 + 2]){ max = n * 2 + 2; //跟新最小的值 } } if(arr[n] > arr[max]){ break;//顺序正确，不需要再调整 }else{ b = arr[n]; arr[n] = arr[max]; arr[max] = b; n = max; } } } //堆排序 void stack(int arr[], int length){ start_time = clock(); int i,k,m = 0; for(i = length/2-1; i >=0; i--){ adjust(arr,i,length-1); } //调整堆 for(i = length-1 ;i >= 0; i--){ //调整后把最后一个和第一个交换，每次调整少一个元素，依次向前 k = arr[i]; arr[i] = arr[0]; arr[0] = k; adjust(arr,0,i-1); } end_time = clock(); times = static_cast<double>(end_time-start_time)/CLOCKS_PER_SEC*1000; cout <<right ; cout <<setw(7) <<times<<"ms"; } //归并排序合并函数 void mergeSoft(int a[], int first, int mid, int last, int temp[]){ int i = first, j = mid + 1; int m = mid, n = last; int k = 0; while (i <= m && j <= n){ if (a[i] <= a[j]){ temp[k++] = a[i++]; }else{ temp[k++] = a[j++]; } } while (i <= m){ temp[k++] = a[i++]; } while (j <= n){ temp[k++] = a[j++]; } for (i = 0; i < k; i++){ a[first + i] = temp[i]; } } //归并排序递归拆分函数 void mergerSelf(int arr[], int left, int right, int arrTmp[]){ if(left < right){ int center = (left + right)/2; mergerSelf(arr, left, center, arrTmp); mergerSelf(arr, center+1, right, arrTmp); mergeSoft(arr, left, center, right, arrTmp); } } //归并排序 void merger(int arr[], int n){ start_time = clock(); int *arrTmp = new int[n]; mergerSelf(arr, 0, n - 1, arrTmp); delete[] arrTmp; //记录时间 end_time = clock(); times = static_cast<double>(end_time-start_time)/CLOCKS_PER_SEC*1000; cout <<right ; cout <<setw(7) <<times<<"ms"; } //快速排序的元素移动 int fastSort(int arr[], int left, int right){ int center = (left+right)/2; int num = arr[center]; //记录中枢点的位置，这里选择最左边点当做中枢点 while(left < right){ //比枢纽小的移动到左边 while(left < right && arr[right] >= num){ right--; //一直到有一个元素小于所选关键中枢为止 } arr[left] = arr[right]; while(left < right && arr[left] <= num){ left++; //一直到有一个元素大于所选关键中枢为止 } arr[right] = arr[left]; //关键字入列 } arr[left] = num; return left; } //快速排序递归划分 int fastSortSelf(int arr[], int left, int right){ if(left < right){ int lowLocation = fastSort(arr,left,right); //第一个指针的位置 fastSortSelf(arr,left,lowLocation - 1); fastSortSelf(arr,lowLocation + 1,right); } } //快速排序 void fast(int arr[], int n){ start_time = clock(); fastSortSelf(arr,0,n-1); //记录时间 end_time = clock(); times = static_cast<double>(end_time-start_time)/CLOCKS_PER_SEC*1000; cout <<right ; cout <<setw(7) <<times<<"ms"; } int main(){ cout<<" ****************************整数最坏（逆序）测试*********************** "; cout<<"数据量 冒泡 选择 插入 希尔 堆 归并 快速 "; int size; //记录每个测试数量 int tmpNum; //记录临时数 int arr1[8] = {49,38,65,97,76,13,27,49}; //测试数据的各个范围 int nums[6] = {100,1000,5000,10000,30000,50000}; /* printfArr(arr1,8); printf(" "); fast(arr1,8); printfArr(arr1,8);*/ for(int p = 0; p < 6; p++){ size = nums[p]; int arrs1[size],arrs2[size],arrs3[size],arrs4[size],arrs5[size],arrs6[size],arrs7[size]; cout<<left; cout <<"n="<<setw(6)<<size; //产生有序数 for(int m = 0; m < size; m++){ int tmpNum = size - m; arrs1[m] = tmpNum; arrs2[m] = tmpNum; arrs3[m] = tmpNum; arrs4[m] = tmpNum; arrs5[m] = tmpNum; arrs6[m] = tmpNum; arrs7[m] = tmpNum; } bubbling(arrs1,size); //冒泡排序法 directDialing(arrs2,size);//直接选择排序 insert(arrs3,size); //直接插入排序 Heer(arrs4,size); //希尔排序 stack(arrs5,size); //堆排序 merger(arrs6,size); //归并排序 fast(arrs7,size); //快速排序 cout<<" "; } //*****************随机数测试法****************** int number; int nlong; //数据量 cout<<" ******************************随机数测试******************************* "; cout<<"数据量 冒泡 选择 插入 希尔 堆 归并 快速 "; for(int r = 0; r < 6; r++){ size = nums[r]; int rands1[size],rands2[size],rands3[size],rands4[size],rands5[size],rands6[size],rands7[size]; //产生测试随机数 srand((unsigned) time(NULL)); for (int rd = 0; rd < size; rd++){ tmpNum = rand() % size; rands1[rd] = tmpNum; rands2[rd] = tmpNum; rands3[rd] = tmpNum; rands4[rd] = tmpNum; rands5[rd] = tmpNum; rands6[rd] = tmpNum; rands7[rd] = tmpNum; } //输出测试数据量 cout<<left; cout <<"n="<<setw(6)<<size; //依次调用各个排序函数 bubbling(rands1,size); //冒泡排序法 directDialing(rands2,size);//直接选择排序 insert(rands3,size); //直接插入排序 Heer(rands4,size); //希尔排序 stack(rands5,size); //堆排序 merger(rands6,size); //归并排序 fast(rands7,size); //快速排序 cout<<" "; } }
参考资料：
http://www.cnblogs.com/zyf-zhaoyafei/p/4658333.html
http://www.cnblogs.com/vamei/archive/2013/03/12/2948847.html
http://www.cnblogs.com/wolf-sun/p/4312475.html
http://www.cnblogs.com/liuling/p/2013-7-24-01.html
http://www.cnblogs.com/kkun/archive/2011/11/23/2260286.html