首页 > 代码库 > 总结N种排序算法及实现
总结N种排序算法及实现
排序算法是一个简单的问题，但在此问题上却有大量的研究！当前的排序算法通常按照如下四个方面进行分类（或是评价）：
1、时间复杂度：一个排序算法的理想性能是O(n)。一般而言，好的性能O(nlogn)，坏的性能O(n2)。
2、空间复杂度（内存使用量）
3、稳定性：稳定的排序算法会让原本有相等键值的记录维持原本的相对次序。
4、排序方式：插入、交换、选择、合并等
一、冒泡排序：这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
步骤：1、比较相邻的两个元素，如果第一个比第二个大，就交换顺序。
2、对每一对做1、中的操作。一趟就把最大元素沉底。
3、不断从头重复2、中的操作（不必比较上一趟的最后一个元素，因为它已经沉底），直到最后一个元素沉底。
时间复杂度：O(n2)
稳定性：稳定
排序方式：交换
程序实现：
1 //维基百科的冒泡排序java实现 2 public void BubbleSort2(){ 3 int temp = 0; 4 for (int i = 0; i < N; i++) { 5 for (int j = 0; j < N-1-i; j++) { 6 if(a[j]>a[j+1]) 7 { 8 temp = a[j]; 9 a[j] = a[j+1];10 a[j+1] = temp;11 }12 }13 }14 }15 //冒泡排序16 public void BubbleSort(){17 int k = N;18 int i = 0;19 int j = 1;20 while(k>0)21 {22 while(j<k)23 {24 if(a[i]>a[j])25 {26 int temp = a[i];27 a[i] = a[j];28 a[j] = temp;29 }30 i++;31 j++;32 }33 k--;34 j = 1;35 i = 0;36 }37 }
二、选择排序：简单直观的算法。
步骤：
1、重复该过程：从未排序的序列中选取最小的元素未排序序列的放到起始位置，并将该元素标志位排序后的序列。
时间复杂度：O(n2)
稳定性：稳定
排序方式：选择
程序实现：
//选择排序 public void SelectSort(){ int min = 0; int mintemp = 0; for (int i = 0; i < N; i++) { for(int j = i+1;j < N;j++){ if(a[min] > a[j]) { min = j; } } mintemp = a[i]; a[i] = a[min]; a[min] = mintemp; } }
三、插入排序：是简单直观的算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入，需要反复把已排序元素逐步向后挪位，为最新 元素提供插入空间。
步骤：
1、从第一个元素开始，认为该元素为已排序列。
2、取出下一个元素，在已排序列中从后向前扫描。
3、如果该元素大于新元素，将该元素向后移动一个位置。
4、重复步骤3，直到找到不大于新元素的位置。
5、将新元素插入到该元素后。
6、重复步骤2-5，直到最后一个元素安放。
时间复杂度：O(n2)
排序方式：插入
稳定性：稳定
程序实现：
1 //插入排序 2 public void InsertSort(){ 3 for (int i = 1; i < N; i++) 4 { 5 int temp = a[i]; 6 int position = i; 7 while(position>0 && a[position-1]>temp){ 8 a[position] = a[position-1]; 9 position--;10 }11 a[position] = temp;12 }13 }
四、归并排序：分治法的一个典型应用。将两个已排序的串合并成一个串行的操作。
步骤：
1、申请空间，使其大小为已经排序串行之和，该空间用来存放合并后的串行。
2、设定两个指针，最初位置分别为已排序串行的起始位置。
3、比较两个指针所指向的对象，选择小的放到合并空间，并移动指针到下一个位置。
4、重复第3个步骤，直到某一个指针到达串尾部
5、将指针未到尾部的串行的剩下元素直接复制到合并串尾部。
时间复杂度：O(nlogn)
空间复杂度：O(n)
稳定性：稳定
排序方式：归并
程序实现：
1 1 //归并排序--递归 2 2 public int[] MergeSort(int[] arr){ 3 3 if(arr.length <= 1) 4 4 { 5 5 return(arr); 6 6 } 7 7 int ahalf = arr.length/2; 8 8 int bhalf = arr.length-ahalf; 9 9 int [] arr1 = new int[ahalf];10 10 int [] arr2 = new int[bhalf];11 11 System.arraycopy(arr, 0, arr1, 0, ahalf);12 12 System.arraycopy(arr, ahalf, arr2, 0, bhalf);13 13 arr1 = MergeSort(arr1);14 14 arr2 = MergeSort(arr2);15 15 return MergeSortSub(arr1, arr2);16 16 17 17 }18 18 //归并排序子程序19 19 public int[] MergeSortSub(int[] A,int[] B){20 20 int [] temp = new int[A.length + B.length];21 21 int i=0,j=0,k=0;22 22 while(i<A.length && j<B.length)23 23 {24 24 if(A[i]<B[j])25 25 {26 26 temp[k] = A[i];27 27 i++;28 28 }29 29 else {30 30 temp[k]=B[j];31 31 j++;32 32 }33 33 k++;34 34 }35 35 while(i<A.length){36 36 temp[k] = A[i];37 37 i++;38 38 k++;39 39 }40 40 while(j < B.length)41 41 {42 42 temp[k] = B[j];43 43 j++;44 44 k++;45 45 }46 46 return temp;47 47 }
五、快速排序：快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。
步骤：
1、从序列中挑出一个元素，称为“基准”（pivot）。
2、重新排列，把所有比基准小的放在左边，比基准大的放到右边（相同的数放到任一边）。在该分区退出后，基准就处于排序后位置。这个称为分区（partition）操作。
3、递归的将左子序列和右子序列快速排序。直至退出。
时间复杂度：平均时间复杂度：O(nlgn)。最坏时间复杂度：O(n2)，但它通常比O(nlogn) 的算法快
空间复杂度：需要额外的O(n)空间。原地分区版本的快速排序，能够达到平均O(lgn)的空间复杂度。
稳定性：不稳定
排序方式：交换
程序实现：
//快速排序-递归 public int[] QuickSort(int[] arr,int p,int r){ if(p<r) { int index = Partition1(arr, p, r); QuickSort(arr, p, index-1); QuickSort(arr, index+1, r); } return arr; } //分区，返回分区后基准元素所在的位置 public int Partition(int[] arr,int p,int r){ int x = arr[r]; int i = p ; for (int j = p; j < r; j++) { if(arr[j] <= x) { swap(arr, i, j); i = i + 1; } } swap(arr, i, r); return i; }
六、希尔排序：也称递减增量排序算法，是插入排序的一种更高效的改进版本。它是基于插入排序的以下两点性质提出的改进方法：
1、插入排序在对几乎已经排好序的数据操作时，效率很高，几乎能够达到线性排序的效率。
2、但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。
步骤：
1、希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素一次性的朝最终位置前进一大步。
2、然后算法再取越来越小的步长进行排序，最后一步，步长为1，也就是插入排序。但是，到达这一步，需要排序的数据几乎排好了，此时插入排序很快。
更好的理解描述：将数组列在一个表中，并对列进行排序（插入排序）。重复此过程，不过，每次（减少列数）用更长的列来进行。最后整个表就只有一列。
步长选择是希尔排序的重要部分，需要保证最后一次排序的步长为1。目前已知的最好步长序列(1,5,19,41,109...)。还有一个在大数组排序中表现优异的是斐波那契数列（除去0和1，将剩余的数以黄金分区比的两倍的幂进行运算得到的数列）
时间复杂度:O(n1.25)
稳定性：不稳定
排序方式：插入排序
程序实现：
public void ShellSort(){ int h =1; while(h < a.length/3){ //确定最大步长 h = h*3+1; } for(;h>=1;h/=3) { //每次步长变成上一个步长的1/3 ....,121,40,13,4,1 for(int k = 0;k < h;k++) { // 对h列的每一列进行排序（插入） for(int i = h+k;i<a.length;i+=h) { for (int j = i; j >= h+k && a[j] < a[j-h]; j-=h) { swap(a, j, j-h); } } } } }
七、基数排序：它是一种非比较型整数排序算法，将整数按照位数切割成不同的数字，然后按每个位数分别比较。
步骤：
1、将所有待比较的数值（正整数）统一为同样的数位长度，数位较短的前面补0。
2、从最低位开始，依次进行一次排序。
3、从最低位排序一直到最高位排序完成后，数列就变成一个有序序列。
时间复杂度：O(kn)，其中n是排序元素个数，k是数字位数。k决定了该算法的时间复杂度。一般情况下，基数排序要快过基于比较的排序，比如快速排序。
稳定性：稳定
排序方式：分布
程序实现：
1 //基数排序 2 public void RadixSort(){ 3 4 int max = a[GetIndex_Max()]; 5 int exp = 1; 6 while(max/exp > 0){ 7 int mmax = (a[0]/exp)%10; 8 int mmin = (a[0]/exp)%10; 9 int [] b = new int[N];10 for(int m = 0;m < a.length;m++)11 {12 if((a[m]/exp)%10 > mmax)13 {14 mmax = (a[m]/exp)%10;15 }16 if((a[m]/exp)%10 < mmin)17 {18 mmin = (a[m]/exp)%10;19 }20 }21 int [] bucket = new int[mmax - mmin +1]; 22 23 for (int i = 0; i < a.length; i++) {24 bucket[(a[i]/exp)%10-mmin]++; 25 }26 for (int j = 1; j < bucket.length; j++) {27 bucket[j] = bucket[j-1] + bucket[j];28 }29 for(int k = a.length-1;k >= 0;k--)30 {31 b[bucket[(a[k]/exp)%10-mmin] - 1] =a[k];32 bucket[(a[k]/exp)%10-mmin] -= 1;33 }34 exp = exp * 10;35 a = b;36 }37 38 39 }
八、计数排序：使用一个额外的的数组C，其中第i个元素是待排序数列中值等于i的个数，然后根据数组C将A中的元素排到正确的位置。
步骤：
1、找出待排序数组中的最大和最小的元素。
2、统计数组中每个值为i的元素出现的次数，存储在数组C中的第i项
3、对所有的计数累加（从c中的第一个元素开始，每一项和前一项相加）
4、反向填充目标数组：将每个元素i放在新数组的第C[i]项，每放一个元素就将C[i]减去1。
时间复杂度：当输入的n个元素是0到k之间的整数时，它的运行时间是O(n+k)，排序速度快于任何比较排序的算法。
空间复杂度：用来计数的数组C的长度取决于待排序数组中数据的范围（最大值与最小值的差加1），这使得计数排序对数据范围较大的数组，需要大量的空间。但是，计数排序用于基数排 序中，能够优劣互补。
稳定性：稳定
排序方式：分布
程序实现：
1 //计数排序 2 public void CountingSort(){ 3 //1、找出待排序数组中的最大和最小的元素。 4 int min = a[0]; 5 int max = a[0]; 6 for(int i = 0;i < N;i++) 7 { 8 if(a[i] < min) 9 {10 min = a[i];11 }12 if(a[i] > max)13 {14 max = a[i];15 }16 }17 //2、统计数组中每个值为i的元素出现的次数，存储在数组C中的第i项18 int [] C = new int[max - min +1];19 for(int j = 0;j < N;j++)20 {21 C[a[j]]++ ;22 }23 //对所有的计数累加（从c中的第一个元素开始，每一项和前一项相加）24 for(int k = 1;k < C.length;k++)25 {26 C[k] = C[k] + C[k-1];27 }28 //反向填充目标数组：将每个元素i放在新数组的第C[i]项，每放一个元素就将C[i]减去1。29 int [] b = new int[N];30 for(int m = 0;m < N;m++)31 {32 b[C[a[m]]-1] = a[m];33 C[a[m]] -= 1;34 }35 a = b;36 }
九、堆排序：利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全完全二叉树的结构，并同时满足堆积的性质：子结点的键值总是小于（大于）它的父节点。
堆：子节点的键值总是小于（大于）它的父节点。
在完全二叉树中，根编号为1，给定某个结点的下标i，其父节点的下标是：Parent[i] = floor(i/2);i的左孩子的下标是：Left[i] = 2i ；右孩子的下标是：Right[i] = 2i+1。
在堆中，最大值总是位于根节点，定义三种基本的操作：
1、保持最大堆性质（堆调整）
2、创建最大堆
3、堆排序：卸载根节点，并做堆调整，保持最大堆性质。
这三种基本操作即可完成堆排序的过程。
时间复杂度：O(nlogn)
空间复杂度：O(1)
稳定性：不稳定
排序方式：选择排序
程序实现：
1 int heap_size = 0; 2 //堆排序数组 3 public void HeapSortArray() 4 { 5 heap_size = a.length; 6 HeapSort(a); 7 } 8 //堆排序 9 public void HeapSort(int [] a)10 {11 int temp = 0;12 Build_Max_Heap(a);13 for (int i = heap_size - 1; i >= 0; i--) {14 temp = a[0];15 a[0] = a[i];16 a[i] = temp;17 //Exchange(a[0], a[i]);18 heap_size = heap_size - 1;19 Max_Heapify(a, 0); 20 }21 }22 //建立最大堆23 public void Build_Max_Heap(int [] a)24 {25 for(int i = (heap_size - 2)/2;i>=0;i--)26 {27 Max_Heapify(a, i);28 }29 }30 //保持最大堆性质31 //输入为一个数组a和一个下标i,假设left[i] 和 right[i]都是最大堆，而a[i]小于其子女， 违反最大堆性质，要调整32 public void Max_Heapify(int [] a , int i)33 {34 int temp = 0;35 int left = 2*i + 1;36 int right = 2*(i + 1);37 int largest = 0;38 if (left < heap_size && a[left]>a[i])39 {40 largest = left;41 }42 else43 {44 largest = i;45 }46 if(right < heap_size && a[right]>a[largest])47 {48 largest = right;49 }50 if(largest != i)51 {52 temp = a[i];53 a[i] = a[largest];54 a[largest] = temp;55 56 //Exchange(a[i],a[largest]);57 Max_Heapify(a, largest);58 }59 }
九种常见的排序方式算是写完了，其他的排序算法还有很多，有机会再写，拜拜！
总结N种排序算法及实现