经典排序算法解析

    许多高级语言中都提供有排序函数，但是掌握一些经典排序算法的基本原理和编码方法还是很有必要，这个学习过程可以帮助我们更好的理解每种排序算法的设计思路，本篇博客将介绍9种十分经典的排序算法，提供了解释性语言JavaScript与编译型语言C的源代码。

一、直接插入排序

    直接插入排序是最简单的一种排序算法，也最容易理解。它的核心思想为将元素逐个插入一个有序的数列中。用文字描述可以分为如下几步：

1.把数列中的第一个元素取出，作为有序数列的起始元素。

2.依次拿数列中的其他元素与有序数列中的元素进行比较，将其插入正确的位置。

用图示描述插入排序如下：

直接插入排序的特点是对新元素的每轮插入前，有序数列中的所有元素都是排序好的，即任意时刻，被排序动过的元素组成的数列都是有序的。

用JavaScript实现的简单插入排序：

//插入排序var array = [1,54,2,64,12,65,76,46,34,98];for(var i = 0;i
    
     0;j--){		if (temp
    

用C实现的简单插入排序：

#include 
    
     void mySort(int array[],int size){	for(int i=0;i
     
      0;j--){			if(temp
     
    

二、二分插入排序(折半插入排序)

    二分插入排序也是插入排序的一种，其又叫做折半插入排序。它与直接插入排序的唯一不同只在于查找插入位置的方式。直接插入排序是通过遍历来查找要插入元素的位置，二分插入排序则是通过二分法来查找要插入的位置，之后将此位置所有元素后移，将排序的元素进行插入。

JavaScript实现的二分插入排序：

var array = [1,54,2,64,12,65,76,46,34,98];//二分插入排序for(var i=0;i
    
     temp) {			right=middle-1;		}else{			left = middle+1;		}	}	for(var j=i+1;j>left;j--){		array[j] = array[j-1];	}	array[left] = temp;}console.log(array);//[ 1, 2, 12, 34, 46, 54, 64, 65, 76, 98 ];
    

C实现的二分插入排序：

#include 
    
     //二分插入排序void mySort(int array[],int size){	for(int i=0;i
     
      temp){				right=middle-1;			}else {				left = middle+1;			}		}		for(int j =i+1;j>left;j--){			array[j] = array[j-1];		}			array[left] = temp;	}}int main(){	int a[] = {1, 2, 12, 34, 46, 54, 64, 65, 76, 98 };	mySort(a,10);	for(int i = 0;i<10;i++){		printf("%d\n",a[i]);	}	return 0;}
     
    

三、希尔排序

    希尔排序也是插入排序的一种，它先将整个数列分割成若干个小的子序列进行插入排序，逐渐减少子序列的个数，直到最后组合成一个数列，完成整个排序过程。希尔排序的过程使用文字描述可以表示为如下几步：

1.假设数列元素个数为n，先取一个小于n的增量d1，将所有间隔d1距离的元素放为1组进行插入排序，d1通常取值n/2，向下取整。

2.再次取d2<d1，将所有间隔d2距离的元素放为1组进行插入排序，通常d2取值为d1/2，向下取整。

3.重复步骤2，直到取得d等于1。

图示希尔排序如下：

JavaScript实现的希尔排序：

var array = [1,54,2,64,12,65,76,46,34,98];//希尔排序//步长 分组数var d = Math.floor(array.length/2);while(d>=1){	//每组元素个数	var counts = Math.floor(array.length/d);	//每组排序依次	for (var i = 0; i < d ; i++) {		//组内的插入排序		for(var j = 0;j
    
     0;k-=d){				if (temp
    

C实现的希尔排序：

#include 
    
     //希尔排序void mySort(int array[],int size){	int d = size/2;	while(d>=1){	//每组元素个数	int counts = size/d;	//每组排序依次	for (int i = 0; i < d ; i++) {		//组内的插入排序		for(int j = 0;j
     
      0;k-=d){				if (temp
     
    

四、选择排序

        前边所说的3种排序算法原理上都是插入排序，即从无序数列中逐个取元素将其插入到有序数列中的合适位置。选择排序则刚好与之相反，其从无序数列中先找到最小值，放在排序数列首部，在依次找到剩余数列的中最小值追加入有序数列，最终完成数列的排序。用文字描述选择排序步骤不如：

1.找到数列中的最小值，将其作为有序数列的第一个元素。

2.从剩余数列中找到最小值，追加入有序数列。

3.重复步骤2，直到排完整个数列。

图示描述选择排序如下：

JavaScript实现的选择排序算法：

var array = [1,54,2,64,12,65,76,46,34,98];//选择排序for(var i=0;i

C实现的选择排序算法：

//选择排序void mySort(int array[],int size){	for(int i=0;i

五、冒泡排序

      冒泡排序和选择排序是我们学习编程课时必不可少的两种排序算法，冒泡排序算法的核心是每次比较相邻的连个元素，如果它们的顺序不对，则进行交换，一轮排序下来，最大值一定被排序到数列的末端。之后除去最后一个元素再进行第二轮冒泡，直到整个数列排序完成。用文字描述冒泡排序的过程如下：

1.从左向右依次比较相邻两元素，如果顺序不对，则进行交换，最终最大的元素被放在最后。

2.除去最后一个元素，重复步骤1，最终剩下元素中最大的被放在倒数第2个位置。

3.继续上面的重复，直到排完整个数列。

JavaScript实现的冒泡排序算法：

var array = [1,54,2,64,12,65,76,46,34,98];//冒泡排序for(var i=0;i
    
     array[j+1]) {			array[j] = array[j+1];			array[j+1] = temp;		}	}}console.log(array);//[ 1, 2, 12, 34, 46, 54, 64, 65, 76, 98 ]
    

C实现的冒泡排序算法：

#include 
    
     //冒泡排序void mySort(int array[],int size){	for(int i =0;i
     
      array[j+1]){				array[j] = array[j+1];				array[j+1] = temp;			}		}	}}int main(){	int a[] = {1, 2, 12, 34, 46, 54, 64, 65, 76, 98};	mySort(a,10);	for(int i = 0;i<10;i++){		printf("%d\n",a[i]);	}	return 0;}
     
    

六、双向冒泡排序

    双向冒泡排序是冒泡排序的一种变体，冒泡排序每次比较都是从左向右，找出最大的放在最后。双向冒泡排序则是第一轮从左向右将最大的放最后，第二轮从右向左将最小的放最首，如此交替直到整个数列排序完成。文字描述双向冒泡排序步骤如下：

1.从左向右依次比较相邻两个元素，如果顺序不对，则进行交换，如此一轮下来，最大的元素在最后。

2.除去已经排序好的元素，从右向左依次比较相邻的两个元素，如果顺序不对，则进行交换，最小的元素在首部。

3.交替重复步骤1与步骤2直到排序完成。

双向冒泡排序示意图如下：

JavaScript实现的双向冒泡排序算法：

var array = [1,54,2,64,12,65,76,46,34,98];//双向冒泡排序var start = 0;var end = array.length;while(end-start>0){	//从左向右冒泡	for(var i=start;i
    
     start+1;j--){		var temp = array[j];		if (array[j-1]>temp) {			array[j] = array[j-1];			array[j-1] = temp;		}	}	start++;}console.log(array);//[ 1, 2, 12, 34, 46, 54, 64, 65, 76, 98 ]
    

C实现的双向冒泡排序算法：

#include 
    
     //双向冒泡排序void mySort(int array[],int size){	int start = 0;	int end = size;	//从左向右冒泡	for(int i=start;i
     
      start+1;j--){		int temp = array[j];		if (array[j-1]>temp) {			array[j] = array[j-1];			array[j-1] = temp;		}	}	start++;}int main(){	int a[] = {1, 2, 12, 34, 46, 54, 64, 65, 76, 98,33};	mySort(a,11);	for(int i = 0;i<11;i++){		printf("%d\n",a[i]);	}	return 0;}
     
    

七、快速排序算法

    快速排序算法和基本思路是通过一趟排序将数列分成两部分，其中一部分的所有数据都比另一部分小。之后在分别在两个子数列中进行递归，直到最终排序完成。快速排序算法的核心是递归，因此其效率十分高。用文字描述快速排序的步骤如下：

1.随机取一个元素作为基准，将小于此元素的数据都放在此元素的左侧，大于此元素的数据都放在此元素的右侧，将数列分隔成左右两个子数列。

2.分别对左右子数列进行步骤1的递归，直到数列长度为1或者0，表示排序完成。

JavaScript实现的快速排序算法：

var array = [1, 54, 2, 64, 12, 65, 76, 46, 34, 98, 34];//快速排序function sort(array, left, right) {	if (right - left >= 1) {		//取第一个元素作为基准		let base = array[left];		let i = left + 1;		let index = left;		while (i <= right) {			//大于等于的已经在右边 不需要修改 小于的要放在左边			if (array[i] < base) {				if (index + 1 == i) {					//交换					array[index] = array[i];					array[i] = base;					index++;				} else {					//先将base与其后一个元素交换					array[index] = array[index + 1];					array[index + 1] = base;					//交换					let temp = array[index];					array[index] = array[i];					array[i] = temp;					index++;				}			}			i++;		}		//递归排序		sort(array, left, index - 1);		sort(array, index + 1, right);	}}sort(array, 0, array.length - 1);console.log(array); //[ 1, 2, 12, 34,34, 46, 54, 64, 65, 76, 98 ]

C语言实现的快速排序：

#include 
    
     //快速排序void mySort(int array[],int left,int right){	if(right-left>=1){		int base = array[left];		int i = left+1;		int index = left;		while(i<=right){			if(array[i]
    

八、堆排序

    堆排序是比快速排序更加复杂的一种排序算法。堆排序使用到了堆这样一种数据结构。首先我们需要搞清楚什么是堆结构。堆是一种类似完全二叉树，同时又满足如下条件的数据结构：所有子节点的值总是小于(大于)父节点。所有子节点的值都小于父节点的堆叫大顶堆，所有子节点都大于父节点的堆叫小顶堆。

    二叉树你应该比较熟悉，下图就是一个小顶堆的示例：

此二叉树中任何一个子节点的值都是大于父节点。如何将数列构造成这样一个堆结构呢，其实十分简单，将数列按照从上到下，从左到右的原则来构造完全二叉树即可。例如如下数列[1, 54, 2, 64, 12, 65, 76, 46, 34, 98, 34]如果将其构造成堆如下图所示：

正常情况下，这个由数组映射成的二叉树并不符合我们堆的要求，否则也就不需要我们用算法来排序了。要让这个二叉树符合要求，我们需要进行整理，即从末节点开始进行调整，例如先从12，98，34中找到最小的，放在现在12所在的位置，然后从64，46，34中找到最小的元素进行上浮，接着再一层层上浮上去，直到堆顶元素为所有元素中的最小元素。整理完成后，我们只需要将堆顶元素和最后一个元素进行交换，之后除掉最后一个元素再进行堆整理，整理完成后再将顶元素(此时为第2小)与倒数第二个元素交换，依次进行下去，即可完成数列的排序。

    用文字描述堆排序步骤如下：

1.先将数列整理成符合要求的堆。

2.将首末元素交换。

3.除掉最后一个元素在进行堆的整理。

4.重复进行2和3，直到数列排序完成。

JavaScript实现的堆排序算法：

var array = [1, 54, 2, 64, 12, 65, 76, 46, 34, 98, 34];//堆排序//堆调整 大顶function store(array,index,end){	let top = array[index];	let left;	let right;	if (index*2+1<=end) {		left = index*2+1;	}else{		//没有左子树 说明已经是叶子节点		//无需调整直接return		return;	}	if (index*2+2<=end) {		right = index*2+2;	}else{		//没有右子树 调整左子树即可		if (array[left]>top) {			array[index] = array[left];			array[left] = top;			top = array[index];		}		return;	}	//找出堆单元中的最大值	if (array[left]>top) {		array[index] = array[left];		array[left] = top;		top = array[index];			}	if (array[right]>top) {		array[index] = array[right];		array[right] = top;		top = array[index];	}}function sort(array,end){	//先将堆进行调整 倒叙调整	let i = end;	while(i>=0){		store(array,i,end)		i--;	}	//根节点一定是最大的 放最后 再进行堆整理	let temp = array[end];	array[end] = array[0];	array[0] = temp;	end--;	if (end>0) {		sort(array,end);	}else{		return;	}	}sort(array, array.length-1);console.log(array); //[ 1, 2, 12, 34,34, 46, 54, 64, 65, 76, 98 ]

C语言实现的堆排序算法：

#include 
    
     void store(int array[],int index,int end){	int top = array[index];	int left;	int right;	if (index*2+1<=end) {		left = index*2+1;	}else{		//没有左子树 说明已经是叶子节点		//无需调整直接return		return;	}	if (index*2+2<=end) {		right = index*2+2;	}else{		//没有右子树 调整左子树即可		if (array[left]>top) {			array[index] = array[left];			array[left] = top;			top = array[index];		}		return;	}	//找出堆单元中的最大值	if (array[left]>top) {		array[index] = array[left];		array[left] = top;		top = array[index];			}	if (array[right]>top) {		array[index] = array[right];		array[right] = top;		top = array[index];	}}void mySort(int array[],int end){	//先将堆进行调整 倒叙调整	int i = end;	while(i>=0){		store(array,i,end);		i--;	}	//根节点一定是最大的 放最后 再进行堆整理	int temp = array[end];	array[end] = array[0];	array[0] = temp;	end--;	if (end>0) {		mySort(array,end);	}else{		return;	}	}int main(){	int a[] = {1, 2, 12, 34, 46, 54, 64, 65, 76, 98,34};	mySort(a,10);	for(int i = 0;i<11;i++){		printf("%d\n",a[i]);	}	return 0;}
    

需要注意，大顶堆排序完成后为升序，小顶堆排序完成后为降序。

九、归并排序

    归并排序的核心并不是交换元素的顺序，而是将数列分成多个有序小数列，将相邻的小数列进行归并。文字描述归并排序步骤如下：

1.把长度为n的数列分成长度为1的n个数列。

2.相邻数列进行排序归并。

3.重复操作2，直到所有数列归并成1个整体。

JavaScript实现的归并排序算法：

var array = [1, 54, 2, 64, 12, 65, 76, 46, 34, 98, 34];//归并排序function mergeArray(arrL,arrR){	var tempArray = new Array();	let i = 0;	let j = 0;	while(i
    
     1) {		let arrL = array.slice(0,Math.floor(array.length/2));		let arrR = array.slice(Math.floor(array.length/2),array.length);		if (arrL.length>1) {			arrL = sort(arrL);		}		if (arrR.length>1) {			arrR = sort(arrR);		}		return mergeArray(arrL,arrR);		}	return array;}console.log(sort(array)); //[ 1, 2, 12, 34,34, 46, 54, 64, 65, 76, 98 ]
    

C语言实现的归并排序算法：

#include 
    
     void merge(int array[],int temp[],int start,int end,int middle){	int i=start,j=middle+1,k=start;	while(i