各种常用的排序算法
算法概述
算法分类
十种常见排序算法可以分为两大类：
算法复杂度
相关概念
稳定：如果 a 原本在 b 前面，而 a=b，排序之后 a 仍然在 b 的前面。
不稳定：如果 a 原本在 b 的前面，而 a=b，排序之后 a 可能会出现在 b 的后面。
时间复杂度：对排序数据的总的操作次数。反映当 n 变化时，操作次数呈现什么规律。
空间复杂度： 是指算法在计算机
内执行时所需存储空间的度量，它也是数据规模 n 的函数。
1、冒泡排序（Bubble Sort）
冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
1.1 算法描述
1.2 动图演示
1.3 代码实现
C/C++实现：
//冒泡排序 void bubble_sort(int a[], int n) {//n为a[]的实际长度-1，例如a[4]={3,2,9,10} n为3 int i,j,tem; for (i=0; i<n; i++) for (j=0; j<n-i; j++) //如果左边大于右边则将他们调换位置 if (a[j] > a[j+1])tem=a[j],a[j]=a[j+1],a[j+1]=tem;}
复制代码
Java 实现：
//冒泡排序算法 private static void bubble_sort(int a[], int n) {//n为a[]的实际长度-1，例如a[4]={3,2,9,10} n为3 for (int i=0; i<n; i++) for (int j=0; j<n-i; j++) //如果左边大于右边则将他们调换位置 if (a[j] > a[j+1]) { int tem=a[j];a[j]=a[j+1];a[j+1]=tem; } }
复制代码
2、选择排序（Selection Sort）
选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
2.1 算法描述
n 个记录的直接选择排序可经过 n-1 趟直接选择排序得到有序结果。具体算法描述如下：
2.2 动图演示
2.3 代码实现
C/C++实现：
//选择排序 void selection_sort (int a[], int n) {//n为a[]的实际长度-1，例如a[4]={3,2,9,10} n为3 for(int i=0;i<=n;i++) for(int j=i+1;j<=n;j++) if(a[i]>a[j]){int tem=a[i];a[i]=a[j];a[j]=tem;}}
复制代码
Java 实现：
//选择排序 public static void selection_sort (int a[], int n) {//n为a[]的实际长度-1，例如a[4]={3,2,9,10} n为3 for(int i=0;i<=n;i++) //每次选出第i小的数 for(int j=i+1;j<=n;j++)//与后面没排序的依次比较 选出当前最小的数 if(a[i]>a[j]){int tem=a[i];a[i]=a[j];a[j]=tem;} }
复制代码
2.4 算法分析
表现最稳定的排序算法之一，因为无论什么数据进去都是 O(n2)的时间复杂度，所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。理论上讲，选择排序可能也是平时排序一般人想到的最多的排序方法了吧。
3、插入排序（Insertion Sort）
插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
3.1 算法描述
一般来说，插入排序都采用 in-place 在数组上实现。具体算法描述如下：
从第一个元素开始，该元素可以认为已经被排序；
取出下一个元素，在已经排序的元素序列中从后向前扫描；
如果该元素（已排序）大于新元素，将该元素移到下一位置；
重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置；
将新元素插入到该位置后；
重复步骤 2~5。
3.2 动图演示
3.2 代码实现
C/C++ 实现
//插入排序 void insertion_sort (int a[], int n) {//n为a[]的实际长度-1，例如a[4]={3,2,9,10} n为3 int i,j,tem;//tem 中间临时变量 for (i=1; i<=n; i++) {//当前i与前(i-1)个做比较如果当前i元素小于前(i-1)个,则第(i-1)个向挪一位 for (tem=a[i],j=i-1;j>=0&&tem<a[j];j--)a[j+1]=a[j]; a[j+1]=tem;//确定当前i应该到的位置 }}
复制代码
Java 实现
//插入排序算法： private static void insertion_sort (int a[], int n) {//n为a[]的实际长度-1，例如a[4]={3,2,9,10} n为3 int i,j,tem;//中间临时变量 for (i=1; i<=n; i++) { //当前i与前(i-1)个做比较如果当前i元素小于前(i-1)个,则第(i-1)个向挪一位 for (tem=a[i],j=i-1;j>=0&&tem<a[j];j--)a[j+1]=a[j]; a[j+1]=tem;//确定当前i应该到的位置 } }
复制代码
3.4 算法分析
插入排序在实现上，通常采用 in-place 排序（即只需用到 O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
4、希尔排序（Shell Sort）
1959 年 Shell 发明，第一个突破 O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。
4.1 算法描述
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：
4.2 动图演示
4.3 代码实现
C/C++ 实现：
//希尔排序 void shell_sort(int a[],int n){//n为a[]的实际长度-1，例如a[4]={3,2,9,10} n为3 for(int d=n/2;d>0;d/=2)//d 为增量 for(int i=d;i<=n;i++){ int j=i; int tem=a[j];//j-d 代表 当前j的前一个元素（当前同一个分组） while(j-d>=0&&a[j-d]>tem) a[j]=a[j-d],j=j-d;// 插入排序的方法 a[j]=tem; }}
复制代码
Java 实现：
//希尔排序 private static void shell_sort(int a[],int n){ for(int d=n/2;d>0;d/=2)//d 为增量 for(int i=d;i<=n;i++){ int j=i; int tem=a[j];//j-d 代表 当前j的前一个元素（当前同一个分组） while(j-d>=0&&a[j-d]>tem) {a[j]=a[j-d];j=j-d;}// 插入排序的方法 a[j]=tem; } }
复制代码
4.4 算法分析
希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法（第 4 版）》的合著者 Robert Sedgewick 提出的。
5、归并排序（Merge Sort）
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为 2-路归并。
5.1 算法描述
5.2 动图演示
5.3 代码实现
C/C++实现:
//归并排序void merge_core(int a[],int l,int mid,int r){//合并数组 int k=0,i=l,j=mid+1; int *tem=(int*)malloc(sizeof(int)*(r-l+1));//开临时中间数组 // 执行合并 谁小谁先进tem 两个组比大小 while(i<=mid||j<=r)tem[k++]=((a[i]<a[j]&&i<=mid)||j>r)?a[i++]:a[j++]; while(k--)a[r--]=tem[k]; free(tem);//清除空间 }void merge_sort(int a[],int l,int r){ if(r>l){ int mid=(l+r)>>1;//取中间 一分为二 merge_sort(a,l,mid); merge_sort(a,mid+1,r); merge_core(a,l,mid,r);//合并 }}
复制代码
Java 实现：
//归并排序 private static void mergeSort(int a[],int l,int r){ if(r>l){ int mid=(l+r)>>1;//取中间 一分为二 mergeSort(a,l,mid); mergeSort(a,mid+1,r); mergeCore(a,l,mid,r);//合并 } } private static void mergeCore(int a[],int l,int mid,int r){//合并数组 int k=0,i=l,j=mid+1; int tem[]=new int[r-l+2];//开临时中间数组 // 执行合并 谁小谁先进 两个组比大小 while(i<=mid||j<=r)tem[k++]=(j>r||(i<=mid&&a[i]<a[j]))?a[i++]:a[j++]; while(k!=0)a[r--]=tem[--k]; }
复制代码
5.4 算法分析
归并排序是一种稳定的排序方法。和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 O(nlogn）的时间复杂度。代价是需要额外的内存空间。
6、快速排序（Quick Sort）
快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
6.1 算法描述
快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：
从数列中挑出一个元素，称为 “基准”（pivot）；
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
6.2 动图演示
6.3 代码实现
C/C++实现：
int mp(int a[], int l, int r) { int p = a[r]; while (l<r) { while (l<r && p>a[l])l++;//从左向右寻找比标准p大的数 if(l<r) a[r--]=a[l];//找到了就放到最右边,比标准p大就应该在右边 while (l<r && p<a[r])r--;//从右向左寻找比标准p小的数 if(l<r) a[l++]=a[r];//找到就放到最左边,比标准p大就应该在左边 } a[r]=p; return r; }//快速排序 void quick_sort (int a[], int l, int r) {//r为a[]的实际长度-1，例如a[4]={3,2,9,10} l为0 r为3 if (l < r) { int q = mp(a, l, r);//找到标准应该在的位置 quick_sort(a, l, q-1);//根据标准的位置分为左边部分 quick_sort(a, q+1, r);//根据标准的位置分为右边部分 }}
复制代码
Java 实现：
//快速排序 private static void quickSort(int[] a, int l, int r) {//r为a[]的实际长度-1，例如a[4]={3,2,9,10} l为0 r为3 if(l<r) { int p=mpSort(a,l,r);//找到标准应该在的位置 quickSort(a,l,p-1);//根据标准的位置分为左边部分 quickSort(a,p+1,r);//根据标准的位置分为右边部分 } } private static int mpSort(int[] a, int l, int r) { int p=a[r]; while(l<r) { while(l<r&&p>a[l])l++;//从左向右寻找比标准p大的数 if(l<r)a[r--]=a[l];//找到了就放到最右边,比标准p大就应该在右边 while(l<r&&p<a[r])r--;//从右向左寻找比标准p小的数 if(l<r)a[l++]=a[r];//找到就放到最左边,比标准p大就应该在左边 } a[l]=p; return l; }
复制代码
6.4 算法分析
快速排序算法的时间复杂度和各次标准数据元素的值关系很大。如果每次选取的标准元素都能均分两个子数组的长度.这样的快速排序过程是一个完全二叉树结构。(即每个结点都把当前数组分成两个大小相等的数组结点,n 个元素数组的根结点的分解次数就构成一棵完全二叉树)。这时分解次数等于完全二叉树的深度 log2n 每次快速排序过程无论把数组怎样划分、全部的比较次数都接近于 n-1 次，所以最好情况下快速排序算法的时间复杂度为 O(nlog2n):快速排序算法的最坏情况是数据元素已全部有序，此时数据元素数组的根结点的分需次数构成一棵二叉退化树(即单分支二叉树),一棵二叉退化树的深度是 n.所以最坏情况下快速排序算法的时间复杂度为 O(n2)。般情况下.标准元素值的分布是随机的,这样的二支树的深度接近于 log2n,所以快速排序算法的平均(或称期望)时间复杂度为 O(nlog2n)
7、堆排序（Heap Sort）
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
7.1 算法描述
将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
将堆顶元素 R[1]与最后一个元素 R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足 R[1,2…n-1]<=R[n]；
由于交换后新的堆顶 R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将 R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为 n-1，则整个排序过程完成。
7.2 动图演示
7.3 代码实现
C/C++ 实现：
//大顶堆 void max_heapify(int a[], int l, int r) { int f= l;//建立父节点指标和子节点指标 int s= f*2+1; while (s <=r) { //若子节点指标在范围内才做比较 if (s+1<=r&&a[s]<a[s+1])s++;//先比较两个子节点大小，选择最大的 if (a[f]<a[s]){//如果父节点小于子节点代表需调整，交换父子内容再继续子节点和孙节点比较 int tem=a[f];a[f]=a[s];a[s]=tem; f=s; s=f*2+1;//交换父子内容再继续子节点和孙节点比较 }else return;//调整好了直接跳出 }}//堆排序 void heap_sort(int a[], int n) { for (int i=n/2; i>= 0; i--)max_heapify(a,i,n);//i从最後一个父节点开始调整 //先将第一个元素和已排好元素前一位做交换，再重新调整，直到排序完毕 for (int i=n; i>0;i--) { int tem=a[0];a[0]=a[i];a[i]=tem; max_heapify(a,0,i-1); }}
复制代码
Java 实现：
//堆排序 private static void heapSort(int a[], int n) { for (int i=n/2; i>= 0; i--)maxHeapify(a,i,n);//i从最後一个父节点开始调整 //先将第一个元素和已排好元素前一位做交换，再重新调整，直到排序完毕 for (int i=n; i>0;i--) { int tem=a[0];a[0]=a[i];a[i]=tem; maxHeapify(a,0,i-1); } } //大顶堆 private static void maxHeapify(int a[], int l, int r) { int f= l;//建立父节点指标和子节点指标 int s= f*2+1; while (s <=r) { //若子节点指标在范围内才做比较 if (s+1<=r&&a[s]<a[s+1])s++;//先比较两个子节点大小，选择最大的 if (a[f]<a[s]){//如果父节点小于子节点代表需调整，交换父子内容再继续子节点和孙节点比较 int tem=a[f];a[f]=a[s];a[s]=tem; f=s; s=f*2+1;//交换父子内容再继续子节点和孙节点比较 }else return;//调整好了直接跳出 } }
复制代码
7.4 算法分析
堆排序是一种不稳定排序算法，对于 n 个元素的序列，构造堆过程，需要遍历的元素次数为 O(n)，每个元素的调整次数为 O(log2n)，所以构造堆复杂度为 O(nlog2n)。迭代替换待排序集合首尾元素的次数为 O(n)，每次替换后调整次数为 O(log2n)，所以迭代操作的复杂度为 O(nlog2n)。由此可知堆排序的时间复杂度为 O(nlog2n)，排序过程属于原地排序，不需要额外的存储空间，所以空间复杂度为 O(1)。
8、计数排序（Counting Sort）
计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
8.1 算法描述
找出待排序的数组中最大和最小的元素；
统计数组中每个值为 i 的元素出现的次数，存入数组 C 的第 i 项；
对所有的计数累加（从 C 中的第一个元素开始，每一项和前一项相加）；
反向填充目标数组：将每个元素 i 放在新数组的第 C(i)项，每放一个元素就将 C(i)减去 1。
8.2 动图演示
8.3 代码实现
C/C++实现：
//计数排序 void counting_sort(int a[],int n){ int max_num=0,k=0; //获取最大值 for(int i=1;i<=n;i++)if(a[i]>a[max_num])max_num=i;max_num=a[max_num]; int count[max_num+1]; memset(count,0,sizeof(count));//初始化计数数组 for(int i=0;i<=n;i++)count[a[i]]++;//开始计数 for(int i=0;i<=max_num;i++){ //排序 while(count[i]--)a[k++]=i;//到正确的位置 } }
复制代码
Java 实现：
private static void counting_sort(int a[],int n){ int max_num=0,k=0; //获取最大值 for(int i=1;i<=n;i++)if(a[i]>a[max_num])max_num=i; max_num=a[max_num]; int []count=new int[max_num+1]; //初始化计数数组 for(int i=0;i<=n;i++)count[a[i]]++;//开始计数 for(int i=0;i<=max_num;i++){ //排序 while(0<count[i]--)a[k++]=i;//到正确的位置 } }
复制代码
8.4 算法分析
计数排序是一个稳定的排序算法。当输入的元素是 n 个 0 到 k 之间的整数时，时间复杂度是 O(n+k)，空间复杂度也是 O(n+k)，其排序速度快于任何比较排序算法。当 k 不是很大并且序列比较集中时，计数排序是一个很有效的排序算法。
9、桶排序（Bucket Sort）
桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。
9.1 算法描述
9.2 动图演示
9.3 代码实现
function bucketSort(arr, bucketSize) { if (arr.length === 0) { return arr; } var i; var minValue = arr[0]; var maxValue = arr[0]; for (i = 1; i < arr.length; i++) { if (arr[i] < minValue) { minValue = arr[i]; // 输入数据的最小值 }else if (arr[i] > maxValue) { maxValue = arr[i]; // 输入数据的最大值 } } // 桶的初始化 var DEFAULT_BUCKET_SIZE = 5; // 设置桶的默认数量为5 bucketSize = bucketSize || DEFAULT_BUCKET_SIZE; var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1; var buckets =new Array(bucketCount); for (i = 0; i < buckets.length; i++) { buckets[i] = []; } // 利用映射函数将数据分配到各个桶中 for (i = 0; i < arr.length; i++) { buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]); }
arr.length = 0; for (i = 0; i < buckets.length; i++) { insertionSort(buckets[i]); // 对每个桶进行排序，这里使用了插入排序 for (var j = 0; j < buckets[i].length; j++) { arr.push(buckets[i][j]); } } return arr;}
复制代码
9.4 算法分析
桶排序最好情况下使用线性时间 O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为 O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。
10、基数排序（Radix Sort）
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。
10.1 算法描述
10.2 动图演示
10.3 代码实现
var counter = [];function radixSort(arr, maxDigit) { var mod = 10; var dev = 1; for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) { for(var j = 0; j < arr.length; j++) { var bucket = parseInt((arr[j] % mod) / dev); if(counter[bucket]==null) { counter[bucket] = []; } counter[bucket].push(arr[j]); } var pos = 0; for(var j = 0; j < counter.length; j++) { var value =null; if(counter[j]!=null) { while ((value = counter[j].shift()) !=null) { arr[pos++] = value; } } } } return arr;}
复制代码
10.4 算法分析
基数排序基于分别排序，分别收集，所以是稳定的。但基数排序的性能比桶排序要略差，每一次关键字的桶分配都需要 O(n)的时间复杂度，而且分配之后得到新的关键字序列又需要 O(n)的时间复杂度。假如待排数据可以分为 d 个关键字，则基数排序的时间复杂度将是 O(d*2n) ，当然 d 要远远小于 n，因此基本上还是线性级别的。
基数排序的空间复杂度为 O(n+k)，其中 k 为桶的数量。一般来说 n>>k，因此额外空间需要大概 n 个左右。
评论