阅读此文推荐：前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。

概述

排序有内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。

我们这里说说八大排序就是内部排序。



    

    当n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序序。

   快速排序：是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；



 

1.插入排序—直接插入排序(Straight Insertion Sort)

基本思想:

将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增1的有序表。即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。

要点：设立哨兵，作为临时存储和判断数组边界之用。

直接插入排序示例：



 

如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。

算法的实现：

void print(int a[], int n ,int i){
	cout<<i <<":";
	for(int j= 0; j<8; j++){
		cout<<a[j] <<" ";
	}
	cout<<endl;
}


void InsertSort(int a[], int n)
{
	for(int i= 1; i<n; i++){
		if(a[i] < a[i-1]){               //若第i个元素大于i-1元素，直接插入。小于的话，移动有序表后插入
			int j= i-1;	
			int x = a[i];		 //复制为哨兵，即存储待排序元素
			a[i] = a[i-1];           //先后移一个元素
			while(x < a[j]){	 //查找在有序表的插入位置
				a[j+1] = a[j];
				j--;		 //元素后移
			}
			a[j+1] = x;		 //插入到正确位置
		}
		print(a,n,i);			//打印每趟排序的结果
	}
	
}

int main(){
	int a[8] = {3,1,5,7,2,4,9,6};
	InsertSort(a,8);
	print(a,8,8);
}


 

效率：

 

时间复杂度：O（n^2）.

其他的插入排序有二分插入排序，2-路插入排序。

 

 2. 插入排序—希尔排序（Shell`s Sort）

希尔排序是1959 年由D.L.Shell 提出来的，相对直接排序有较大的改进。希尔排序又叫缩小增量排序

基本思想：

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

操作方法：

选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
	
按增量序列个数k，对序列进行k 趟排序；
	
每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
希尔排序的示例：shell排序的排序过程

假设待排序文件有10个记录，其关键字分别是：49，38，65，97，76，13，27，49，55，04。

增量系列的取值依次为：5，3，1



 

算法实现：

我们简单处理增量序列：增量序列d = {n/2 ,n/4, n/8 .....1} n为要排序数的个数

即：先将要排序的一组记录按某个增量d（n/2,n为要排序数的个数）分成若干组子序列，每组中记录的下标相差d.对每组中全部元素进行直接插入排序，然后再用一个较小的增量（d/2）对它进行分组，在每组中再进行直接插入排序。继续不断缩小增量直至为1，最后使用直接插入排序完成排序。

void print(int a[], int n ,int i){
	cout<<i <<":";
	for(int j= 0; j<8; j++){
		cout<<a[j] <<" ";
	}
	cout<<endl;
}
/**
 * 直接插入排序的一般形式
 *
 * @param int dk 缩小增量，如果是直接插入排序，dk=1
 *
 */

void ShellInsertSort(int a[], int n, int dk)
{
	for(int i= dk; i<n; ++i){
		if(a[i] < a[i-dk]){			//若第i个元素大于i-1元素，直接插入。小于的话，移动有序表后插入
			int j = i-dk;	
			int x = a[i];			//复制为哨兵，即存储待排序元素
			a[i] = a[i-dk];			//首先后移一个元素
			while(x < a[j]){		//查找在有序表的插入位置
				a[j+dk] = a[j];
				j -= dk;			 //元素后移
			}
			a[j+dk] = x;			//插入到正确位置
		}
		print(a, n,i );
	}
	
}

/**
 * 先按增量d（n/2,n为要排序数的个数进行希尔排序
 *
 */
void shellSort(int a[], int n){

	int dk = n/2;
	while( dk >= 1  ){
		ShellInsertSort(a, n, dk);
		dk = dk/2;
	}
}
int main(){
	int a[8] = {3,1,5,7,2,4,9,6};
	//ShellInsertSort(a,8,1); //直接插入排序
	shellSort(a,8);			  //希尔插入排序
	print(a,8,8);
}


 

希尔排序时效分析很难，关键码的比较次数与记录移动次数依赖于增量因子序列d的选取，特定情况下可以准确估算出关键码的比较次数和记录的移动次数。目前还没有人给出选取最好的增量因子序列的方法。增量因子序列可以有各种取法，有取奇数的，也有取质数的，但需要注意：增量因子中除1 外没有公因子，且最后一个增量因子必须为1。希尔排序方法是一个不稳定的排序方法。

 

3. 选择排序—简单选择排序（Simple Selection Sort）

基本思想：

在要排序的一组数中，选出最小（或者最大）的一个数与第1个位置的数交换；然后在剩下的数当中再找最小（或者最大）的与第2个位置的数交换，依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。

简单选择排序的示例：

 

操作方法：

第一趟，从n 个记录中找出关键码最小的记录与第一个记录交换；

第二趟，从第二个记录开始的n-1 个记录中再选出关键码最小的记录与第二个记录交换；

以此类推.....

第i 趟，则从第i 个记录开始的n-i+1 个记录中选出关键码最小的记录与第i 个记录交换，

直到整个序列按关键码有序。


 

算法实现：

void print(int a[], int n ,int i){
	cout<<"第"<<i+1 <<"趟 : ";
	for(int j= 0; j<8; j++){
		cout<<a[j] <<"  ";
	}
	cout<<endl;
}
/**
 * 数组的最小值
 *
 * @return int 数组的键值
 */
int SelectMinKey(int a[], int n, int i)
{
	int k = i;
	for(int j=i+1 ;j< n; ++j) {
		if(a[k] > a[j]) k = j;
	}
	return k;
}

/**
 * 选择排序
 *
 */
void selectSort(int a[], int n){
	int key, tmp;
	for(int i = 0; i< n; ++i) {
		key = SelectMinKey(a, n,i);           //选择最小的元素
		if(key != i){
			tmp = a[i];  a[i] = a[key]; a[key] = tmp; //最小元素与第i位置元素互换
		}
		print(a,  n , i);
	}
}
int main(){
	int a[8] = {3,1,5,7,2,4,9,6};
	cout<<"初始值：";
	for(int j= 0; j<8; j++){
		cout<<a[j] <<"  ";
	}
	cout<<endl<<endl;
	selectSort(a, 8);
	print(a,8,8);
}


 

 简单选择排序的改进——二元选择排序

 

简单选择排序，每趟循环只能确定一个元素排序后的定位。我们可以考虑改进为每趟循环确定两个元素（当前趟最大和最小记录）的位置,从而减少排序所需的循环次数。改进后对n个数据进行排序，最多只需进行[n/2]趟循环即可。具体实现如下：

/** 这是伪函数, 逻辑判断不严谨
void selectSort(int r[],int n) {
	int i ,j , min ,max, tmp;
	for (i=1 ;i <= n/2;i++) {  
		// 做不超过n/2趟选择排序 
		min = i; max = i ; //分别记录最大和最小关键字记录位置
		for (j= i+1; j<= n-i; j++) {
			if (r[j] > r[max]) { 
				max = j ; continue ; 
			}  
			if (r[j]< r[min]) { 
				min = j ; 
			}   
	  }  
	  //该交换操作还可分情况讨论以提高效率
	  tmp = r[i-1]; r[i-1] = r[min]; r[min] = tmp;
	  tmp = r[n-i]; r[n-i] = r[max]; r[max] = tmp; 
 
	} 
}
 */
void selectSort(int a[],int len) {
        int i,j,min,max,tmp;  
        for(i=0; i<len/2; i++){  // 做不超过n/2趟选择排序 
            min = max = i;  
            for(j=i+1; j<=len-1-i; j++){  
				//分别记录最大和最小关键字记录位置
                if(a[j] > a[max]){  
                    max = j;  
                    continue;  
                }  
                if(a[j] < a[min]){  
                    min = j;  
                }  
            }  
			//该交换操作还可分情况讨论以提高效率
            if(min != i){//当第一个为min值，不用交换  
                tmp=a[min];  a[min]=a[i];  a[i]=tmp;  
            }  
            if(min == len-1-i && max == i)//当第一个为max值，同时最后一个为min值，不再需要下面操作  
                continue;  
            if(max == i)//当第一个为max值，则交换后min的位置为max值  
                max = min;  
            if(max != len-1-i){//当最后一个为max值，不用交换  
                tmp=a[max];  a[max]=a[len-1-i];  a[len-1-i]=tmp;  
            }
			print(a,len, i);			
        }  
 }

 

4. 选择排序—堆排序（Heap Sort）

堆排序是一种树形选择排序，是对直接选择排序的有效改进。

基本思想：

堆的定义如下：具有n个元素的序列（k1,k2,...,kn),当且仅当满足



时称之为堆。由堆的定义可以看出，堆顶元素（即第一个元素）必为最小项（小顶堆）。

若以一维数组存储一个堆，则堆对应一棵完全二叉树，且所有非叶结点的值均不大于(或不小于)其子女的值，根结点（堆顶元素）的值是最小(或最大)的。如：

（a）大顶堆序列：（96, 83,27,38,11,09)

  (b)  小顶堆序列：（12，36，24，85，47，30，53，91）



初始时把要排序的n个数的序列看作是一棵顺序存储的二叉树（一维数组存储二叉树），调整它们的存储序，使之成为一个堆，将堆顶元素输出，得到n 个元素中最小(或最大)的元素，这时堆的根节点的数最小（或者最大）。然后对前面(n-1)个元素重新调整使之成为堆，输出堆顶元素，得到n 个元素中次小(或次大)的元素。依此类推，直到只有两个节点的堆，并对它们作交换，最后得到有n个节点的有序序列。称这个过程为堆排序。

因此，实现堆排序需解决两个问题：

1. 如何将n 个待排序的数建成堆；

2. 输出堆顶元素后，怎样调整剩余n-1 个元素，使其成为一个新堆。


首先讨论第二个问题：输出堆顶元素后，对剩余n-1元素重新建成堆的调整过程。

调整小顶堆的方法：

1）设有m 个元素的堆，输出堆顶元素后，剩下m-1 个元素。将堆底元素送入堆顶（（最后一个元素与堆顶进行交换），堆被破坏，其原因仅是根结点不满足堆的性质。

2）将根结点与左、右子树中较小元素的进行交换。

3）若与左子树交换：如果左子树堆被破坏，即左子树的根结点不满足堆的性质，则重复方法 （2）.

4）若与右子树交换，如果右子树堆被破坏，即右子树的根结点不满足堆的性质。则重复方法 （2）.

5）继续对不满足堆性质的子树进行上述交换操作，直到叶子结点，堆被建成。

称这个自根结点到叶子结点的调整过程为筛选。如图：




再讨论对n 个元素初始建堆的过程。

建堆方法：对初始序列建堆的过程，就是一个反复进行筛选的过程。

1）n 个结点的完全二叉树，则最后一个结点是第个结点的子树。

2）筛选从第个结点为根的子树开始，该子树成为堆。

3）之后向前依次对各结点为根的子树进行筛选，使之成为堆，直到根结点。

如图建堆初始过程：无序序列：（49，38，65，97，76，13，27，49）



                             

 算法的实现：

从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数。

void print(int a[], int n){
	for(int j= 0; j<n; j++){
		cout<<a[j] <<"  ";
	}
	cout<<endl;
}



/**
 * 已知H[s…m]除了H[s] 外均满足堆的定义
 * 调整H[s],使其成为大顶堆.即将对第s个结点为根的子树筛选, 
 *
 * @param H是待调整的堆数组
 * @param s是待调整的数组元素的位置
 * @param length是数组的长度
 *
 */
void HeapAdjust(int H[],int s, int length)
{
	int tmp  = H[s];
	int child = 2*s+1; //左孩子结点的位置。(i+1 为当前调整结点的右孩子结点的位置)
    while (child < length) {
		if(child+1 <length && H[child]<H[child+1]) { // 如果右孩子大于左孩子(找到比当前待调整结点大的孩子结点)
			++child ;
		}
		if(H[s]<H[child]) {  // 如果较大的子结点大于父结点
			H[s] = H[child]; // 那么把较大的子结点往上移动，替换它的父结点
			s = child;		 // 重新设置s ,即待调整的下一个结点的位置
			child = 2*s+1;
		}  else {			 // 如果当前待调整结点大于它的左右孩子，则不需要调整，直接退出
			 break;
		}
		H[s] = tmp;			// 当前待调整的结点放到比其大的孩子结点位置上
	}
	print(H,length);
}


/**
 * 初始堆进行调整
 * 将H[0..length-1]建成堆
 * 调整完之后第一个元素是序列的最小的元素
 */
void BuildingHeap(int H[], int length)
{ 
	//最后一个有孩子的节点的位置 i=  (length -1) / 2
	for (int i = (length -1) / 2 ; i >= 0; --i)
		HeapAdjust(H,i,length);
}
/**
 * 堆排序算法
 */
void HeapSort(int H[],int length)
{
    //初始堆
	BuildingHeap(H, length);
	//从最后一个元素开始对序列进行调整
	for (int i = length - 1; i > 0; --i)
	{
		//交换堆顶元素H[0]和堆中最后一个元素
		int temp = H[i]; H[i] = H[0]; H[0] = temp;
		//每次交换堆顶元素和堆中最后一个元素之后，都要对堆进行调整
		HeapAdjust(H,0,i);
  }
} 

int main(){
	int H[10] = {3,1,5,7,2,4,9,6,10,8};
	cout<<"初始值：";
	print(H,10);
	HeapSort(H,10);
	//selectSort(a, 8);
	cout<<"结果：";
	print(H,10);

}



 

分析:

设树深度为k，。从根到叶的筛选，元素比较次数至多2(k-1)次，交换记录至多k 次。所以，在建好堆后，排序过程中的筛选次数不超过下式： 

                                

而建堆时的比较次数不超过4n 次，因此堆排序最坏情况下，时间复杂度也为：O(nlogn )。

 

5. 交换排序—冒泡排序（Bubble Sort）

基本思想：

在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。

冒泡排序的示例：

 

算法的实现：

void bubbleSort(int a[], int n){
	for(int i =0 ; i< n-1; ++i) {
		for(int j = 0; j < n-i-1; ++j) {
			if(a[j] > a[j+1])
			{
				int tmp = a[j] ; a[j] = a[j+1] ;  a[j+1] = tmp;
			}
		}
	}
}

 

冒泡排序算法的改进

对冒泡排序常见的改进方法是加入一标志性变量exchange，用于标志某一趟排序过程中是否有数据交换，如果进行某一趟排序时并没有进行数据交换，则说明数据已经按要求排列好，可立即结束排序，避免不必要的比较过程。本文再提供以下两种改进算法：

1．设置一标志性变量pos,用于记录每趟排序中最后一次进行交换的位置。由于pos位置之后的记录均已交换到位,故在进行下一趟排序时只要扫描到pos位置即可。

改进后算法如下:

void Bubble_1 ( int r[], int n) {
	int i= n -1;  //初始时,最后位置保持不变
	while ( i> 0) { 
		int pos= 0; //每趟开始时,无记录交换
		for (int j= 0; j< i; j++)
			if (r[j]> r[j+1]) {
				pos= j; //记录交换的位置 
				int tmp = r[j]; r[j]=r[j+1];r[j+1]=tmp;
			} 
		i= pos; //为下一趟排序作准备
	 } 
}  


 

2．传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值,我们考虑利用在每趟排序中进行正向和反向两遍冒泡的方法一次可以得到两个最终值(最大者和最小者) , 从而使排序趟数几乎减少了一半。

改进后的算法实现为:

void Bubble_2 ( int r[], int n){
	int low = 0; 
	int high= n -1; //设置变量的初始值
	int tmp,j;
	while (low < high) {
		for (j= low; j< high; ++j) //正向冒泡,找到最大者
			if (r[j]> r[j+1]) {
				tmp = r[j]; r[j]=r[j+1];r[j+1]=tmp;
			} 
		--high;					//修改high值, 前移一位
		for ( j=high; j>low; --j) //反向冒泡,找到最小者
			if (r[j]<r[j-1]) {
				tmp = r[j]; r[j]=r[j-1];r[j-1]=tmp;
			}
		++low;					//修改low值,后移一位
	} 
} 

 

6. 交换排序—快速排序（Quick Sort）

基本思想：

1）选择一个基准元素,通常选择第一个元素或者最后一个元素,

2）通过一趟排序讲待排序的记录分割成独立的两部分，其中一部分记录的元素值均比基准元素值小。另一部分记录的 元素值比基准值大。

3）此时基准元素在其排好序后的正确位置

4）然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。

快速排序的示例：

（a）一趟排序的过程：



（b）排序的全过程



算法的实现：

 递归实现：

void print(int a[], int n){
	for(int j= 0; j<n; j++){
		cout<<a[j] <<"  ";
	}
	cout<<endl;
}

void swap(int *a, int *b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

int partition(int a[], int low, int high)
{
	int privotKey = a[low];								//基准元素
	while(low < high){								    //从表的两端交替地向中间扫描
		while(low < high  && a[high] >= privotKey) --high;  //从high 所指位置向前搜索，至多到low+1 位置。将比基准元素小的交换到低端
		swap(&a[low], &a[high]);
		while(low < high  && a[low] <= privotKey ) ++low;
		swap(&a[low], &a[high]);
	}
	print(a,10);
	return low;
}


void quickSort(int a[], int low, int high){
	if(low < high){
		int privotLoc = partition(a,  low,  high);  //将表一分为二
		quickSort(a,  low,  privotLoc -1);			//递归对低子表递归排序
		quickSort(a,   privotLoc + 1, high);		//递归对高子表递归排序
	}
}

int main(){
	int a[10] = {3,1,5,7,2,4,9,6,10,8};
	cout<<"初始值：";
	print(a,10);
	quickSort(a,0,9);
	cout<<"结果：";
	print(a,10);

}

 

分析：

快速排序是通常被认为在同数量级（O(nlog2n)）的排序方法中平均性能最好的。但若初始序列按关键码有序或基本有序时，快排序反而蜕化为冒泡排序。为改进之，通常以“三者取中法”来选取基准记录，即将排序区间的两个端点与中点三个记录关键码居中的调整为支点记录。快速排序是一个不稳定的排序方法。


快速排序的改进

在本改进算法中,只对长度大于k的子序列递归调用快速排序,让原序列基本有序，然后再对整个基本有序序列用插入排序算法排序。实践证明，改进后的算法时间复杂度有所降低，且当k取值为 8 左右时,改进算法的性能最佳。算法思想如下：

void print(int a[], int n){
	for(int j= 0; j<n; j++){
		cout<<a[j] <<"  ";
	}
	cout<<endl;
}

void swap(int *a, int *b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

int partition(int a[], int low, int high)
{
	int privotKey = a[low];					//基准元素
	while(low < high){					//从表的两端交替地向中间扫描
		while(low < high  && a[high] >= privotKey) --high; //从high 所指位置向前搜索，至多到low+1 位置。将比基准元素小的交换到低端
		swap(&a[low], &a[high]);
		while(low < high  && a[low] <= privotKey ) ++low;
		swap(&a[low], &a[high]);
	}
	print(a,10);
	return low;
}


void qsort_improve(int r[ ],int low,int high, int k){
	if( high -low > k ) { //长度大于k时递归, k为指定的数
		int pivot = partition(r, low, high); // 调用的Partition算法保持不变
		qsort_improve(r, low, pivot - 1,k);
		qsort_improve(r, pivot + 1, high,k);
	} 
} 
void quickSort(int r[], int n, int k){
	qsort_improve(r,0,n,k);//先调用改进算法Qsort使之基本有序

	//再用插入排序对基本有序序列排序
	for(int i=1; i<=n;i ++){
		int tmp = r[i]; 
		int j=i-1;
		while(tmp < r[j]){
			r[j+1]=r[j]; j=j-1; 
		}
		r[j+1] = tmp;
	} 

} 



int main(){
	int a[10] = {3,1,5,7,2,4,9,6,10,8};
	cout<<"初始值：";
	print(a,10);
	quickSort(a,9,4);
	cout<<"结果：";
	print(a,10);

}

 

7. 归并排序（Merge Sort）

基本思想：

归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

归并排序示例：

 

 

合并方法：

设r[i…n]由两个有序子表r[i…m]和r[m+1…n]组成，两个子表长度分别为n-i +1、n-m。

j=m+1；k=i；i=i; //置两个子表的起始下标及辅助数组的起始下标
	
若i>m 或j>n，转⑷ //其中一个子表已合并完，比较选取结束
	
//选取r[i]和r[j]较小的存入辅助数组rf

	如果r[i]<r[j]，rf[k]=r[i]； i++； k++； 转⑵

	否则，rf[k]=r[j]； j++； k++； 转⑵
	
//将尚未处理完的子表中元素存入rf

	如果i<=m，将r[i…m]存入rf[k…n] //前一子表非空

	如果j<=n ,  将r[j…n] 存入rf[k…n] //后一子表非空
	
合并结束。
//将r[i…m]和r[m +1 …n]归并到辅助数组rf[i…n]
void Merge(ElemType *r,ElemType *rf, int i, int m, int n)
{
	int j,k;
	for(j=m+1,k=i; i<=m && j <=n ; ++k){
		if(r[j] < r[i]) rf[k] = r[j++];
		else rf[k] = r[i++];
	}
	while(i <= m)  rf[k++] = r[i++];
	while(j <= n)  rf[k++] = r[j++];
}

 

归并的迭代算法

1 个元素的表总是有序的。所以对n 个元素的待排序列，每个元素可看成1 个有序子表。对子表两两合并生成n/2个子表，所得子表除最后一个子表长度可能为1 外，其余子表长度均为2。再进行两两合并，直到生成n 个元素按关键码有序的表。

void print(int a[], int n){
	for(int j= 0; j<n; j++){
		cout<<a[j] <<"  ";
	}
	cout<<endl;
}

//将r[i…m]和r[m +1 …n]归并到辅助数组rf[i…n]
void Merge(ElemType *r,ElemType *rf, int i, int m, int n)
{
	int j,k;
	for(j=m+1,k=i; i<=m && j <=n ; ++k){
		if(r[j] < r[i]) rf[k] = r[j++];
		else rf[k] = r[i++];
	}
	while(i <= m)  rf[k++] = r[i++];
	while(j <= n)  rf[k++] = r[j++];
	print(rf,n+1);
}

void MergeSort(ElemType *r, ElemType *rf, int lenght)
{ 
	int len = 1;
	ElemType *q = r ;
	ElemType *tmp ;
	while(len < lenght) {
		int s = len;
		len = 2 * s ;
		int i = 0;
		while(i+ len <lenght){
			Merge(q, rf,  i, i+ s-1, i+ len-1 ); //对等长的两个子表合并
			i = i+ len;
		}
		if(i + s < lenght){
			Merge(q, rf,  i, i+ s -1, lenght -1); //对不等长的两个子表合并
		}
		tmp = q; q = rf; rf = tmp; //交换q,rf，以保证下一趟归并时，仍从q 归并到rf
	}
}


int main(){
	int a[10] = {3,1,5,7,2,4,9,6,10,8};
	int b[10];
	MergeSort(a, b, 10);
	print(b,10);
	cout<<"结果：";
	print(a,10);

}

 

两路归并的递归算法

void MSort(ElemType *r, ElemType *rf,int s, int t)
{ 
	ElemType *rf2;
	if(s==t) r[s] = rf[s];
	else
	{ 
		int m=(s+t)/2;			/*平分*p 表*/
		MSort(r, rf2, s, m);		/*递归地将p[s…m]归并为有序的p2[s…m]*/
		MSort(r, rf2, m+1, t);		/*递归地将p[m+1…t]归并为有序的p2[m+1…t]*/
		Merge(rf2, rf, s, m+1,t);	/*将p2[s…m]和p2[m+1…t]归并到p1[s…t]*/
	}
}
void MergeSort_recursive(ElemType *r, ElemType *rf, int n)
{   /*对顺序表*p 作归并排序*/
	MSort(r, rf,0, n-1);
}

8. 桶排序/基数排序(Radix Sort)

说基数排序之前，我们先说桶排序：

基本思想：是将阵列分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的阵列内的数值是均匀分配的时候，桶排序使用线性时间（Θ（n））。但桶排序并不是 比较排序，他不受到 O(n log n) 下限的影响。

         简单来说，就是把数据分组，放在一个个的桶中，然后对每个桶里面的在进行排序。  

 

 例如要对大小为[1..1000]范围内的n个整数A[1..n]排序  

 首先，可以把桶设为大小为10的范围，具体而言，设集合B[1]存储[1..10]的整数，集合B[2]存储   (10..20]的整数，……集合B[i]存储(   (i-1)*10,   i*10]的整数，i   =   1,2,..100。总共有  100个桶。  

  然后，对A[1..n]从头到尾扫描一遍，把每个A[i]放入对应的桶B[j]中。  再对这100个桶中每个桶里的数字排序，这时可用冒泡，选择，乃至快排，一般来说任  何排序法都可以。

  最后，依次输出每个桶里面的数字，且每个桶中的数字从小到大输出，这  样就得到所有数字排好序的一个序列了。  

  假设有n个数字，有m个桶，如果数字是平均分布的，则每个桶里面平均有n/m个数字。如果  

  对每个桶中的数字采用快速排序，那么整个算法的复杂度是  

  O(n   +   m   *   n/m*log(n/m))   =   O(n   +   nlogn   -   nlogm)  

  从上式看出，当m接近n的时候，桶排序复杂度接近O(n)  

  当然，以上复杂度的计算是基于输入的n个数字是平均分布这个假设的。这个假设是很强的  ，实际应用中效果并没有这么好。如果所有的数字都落在同一个桶中，那就退化成一般的排序了。  

        前面说的几大排序算法 ，大部分时间复杂度都是O（n2），也有部分排序算法时间复杂度是O(nlogn)。而桶式排序却能实现O（n）的时间复杂度。但桶排序的缺点是：

        1）首先是空间复杂度比较高，需要的额外开销大。排序有两个数组的空间开销，一个存放待排序数组，一个就是所谓的桶，比如待排序值是从0到m-1，那就需要m个桶，这个桶数组就要至少m个空间。

        2）其次待排序的元素都要在一定的范围内等等。

       桶式排序是一种分配排序。分配排序的特定是不需要进行关键码的比较，但前提是要知道待排序列的一些具体情况。

 

分配排序的基本思想：说白了就是进行多次的桶式排序。

基数排序过程无须比较关键字，而是通过“分配”和“收集”过程来实现排序。它们的时间复杂度可达到线性阶：O(n)。

实例:

扑克牌中52 张牌，可按花色和面值分成两个字段，其大小关系为：

花色： 梅花< 方块< 红心< 黑心  

面值： 2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 < 10 < J < Q < K < A

若对扑克牌按花色、面值进行升序排序，得到如下序列：





即两张牌，若花色不同，不论面值怎样，花色低的那张牌小于花色高的，只有在同花色情况下，大小关系才由面值的大小确定。这就是多关键码排序。

为得到排序结果，我们讨论两种排序方法。
方法1：先对花色排序，将其分为4 个组，即梅花组、方块组、红心组、黑心组。再对每个组分别按面值进行排序，最后，将4 个组连接起来即可。
方法2：先按13 个面值给出13 个编号组(2 号，3 号，...，A 号)，将牌按面值依次放入对应的编号组，分成13 堆。再按花色给出4 个编号组(梅花、方块、红心、黑心)，将2号组中牌取出分别放入对应花色组，再将3 号组中牌取出分别放入对应花色组，……，这样，4 个花色组中均按面值有序，然后，将4 个花色组依次连接起来即可。

设n 个元素的待排序列包含d 个关键码{k1，k2，…，kd}，则称序列对关键码{k1，k2，…，kd}有序是指：对于序列中任两个记录r[i]和r[j](1≤i≤j≤n)都满足下列有序关系：

                                                               

其中k1 称为最主位关键码，kd 称为最次位关键码     。

 

两种多关键码排序方法：

多关键码排序按照从最主位关键码到最次位关键码或从最次位到最主位关键码的顺序逐次排序，分两种方法：

最高位优先(Most Significant Digit first)法，简称MSD 法：

1）先按k1 排序分组，将序列分成若干子序列，同一组序列的记录中，关键码k1 相等。

2）再对各组按k2 排序分成子组，之后，对后面的关键码继续这样的排序分组，直到按最次位关键码kd 对各子组排序后。

3）再将各组连接起来，便得到一个有序序列。扑克牌按花色、面值排序中介绍的方法一即是MSD 法。

最低位优先(Least Significant Digit first)法，简称LSD 法：

1) 先从kd 开始排序，再对kd-1进行排序，依次重复，直到按k1排序分组分成最小的子序列后。

2) 最后将各个子序列连接起来，便可得到一个有序的序列, 扑克牌按花色、面值排序中介绍的方法二即是LSD 法。

 

基于LSD方法的链式基数排序的基本思想

　　“多关键字排序”的思想实现“单关键字排序”。对数字型或字符型的单关键字，可以看作由多个数位或多个字符构成的多关键字，此时可以采用“分配-收集”的方法进行排序，这一过程称作基数排序法，其中每个数字或字符可能的取值个数称为基数。比如，扑克牌的花色基数为4，面值基数为13。在整理扑克牌时，既可以先按花色整理，也可以先按面值整理。按花色整理时，先按红、黑、方、花的顺序分成4摞（分配），再按此顺序再叠放在一起（收集），然后按面值的顺序分成13摞（分配），再按此顺序叠放在一起（收集），如此进行二次分配和收集即可将扑克牌排列有序。   

基数排序:

是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以是稳定的。

算法实现：

Void RadixSort(Node L[],length,maxradix)
{
   int m,n,k,lsp;
   k=1;m=1;
   int temp[10][length-1];
   Empty(temp); //清空临时空间
   while(k<maxradix) //遍历所有关键字
   {
     for(int i=0;i<length;i++) //分配过程
    {
       if(L[i]<m)
          Temp[0][n]=L[i];
       else
          Lsp=(L[i]/m)%10; //确定关键字
       Temp[lsp][n]=L[i];
       n++;
   }
   CollectElement(L,Temp); //收集
   n=0;
   m=m*10;
  k++;
 }
}

 

 

 

总结

各种排序的稳定性，时间复杂度和空间复杂度总结：



 我们比较时间复杂度函数的情况：



 

                             时间复杂度函数O(n)的增长情况



所以对n较大的排序记录。一般的选择都是时间复杂度为O(nlog2n)的排序方法。

 

时间复杂度来说：

(1)平方阶(O(n2))排序

　　各类简单排序:直接插入、直接选择和冒泡排序；

 (2)线性对数阶(O(nlog2n))排序

　　快速排序、堆排序和归并排序；

 (3)O(n1+§))排序,§是介于0和1之间的常数。

       希尔排序

(4)线性阶(O(n))排序

　　基数排序，此外还有桶、箱排序。

说明：

当原表有序或基本有序时，直接插入排序和冒泡排序将大大减少比较次数和移动记录的次数，时间复杂度可降至O（n）；

而快速排序则相反，当原表基本有序时，将蜕化为冒泡排序，时间复杂度提高为O（n2）；

原表是否有序，对简单选择排序、堆排序、归并排序和基数排序的时间复杂度影响不大。

 

稳定性：

排序算法的稳定性:若待排序的序列中，存在多个具有相同关键字的记录，经过排序， 这些记录的相对次序保持不变，则称该算法是稳定的；若经排序后，记录的相对 次序发生了改变，则称该算法是不稳定的。 

     稳定性的好处：排序算法如果是稳定的，那么从一个键上排序，然后再从另一个键上排序，第一个键排序的结果可以为第二个键排序所用。基数排序就是这样，先按低位排序，逐次按高位排序，低位相同的元素其顺序再高位也相同时是不会改变的。另外，如果排序算法稳定，可以避免多余的比较；

稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序

不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序

 

选择排序算法准则：

每种排序算法都各有优缺点。因此，在实用时需根据不同情况适当选用，甚至可以将多种方法结合起来使用。

选择排序算法的依据

影响排序的因素有很多，平均时间复杂度低的算法并不一定就是最优的。相反，有时平均时间复杂度高的算法可能更适合某些特殊情况。同时，选择算法时还得考虑它的可读性，以利于软件的维护。一般而言，需要考虑的因素有以下四点：

1．待排序的记录数目n的大小；

2．记录本身数据量的大小，也就是记录中除关键字外的其他信息量的大小；

3．关键字的结构及其分布情况；

4．对排序稳定性的要求。

设待排序元素的个数为n.

1）当n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序序。

   快速排序：是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；

       堆排序 ：  如果内存空间允许且要求稳定性的，

       归并排序：它有一定数量的数据移动，所以我们可能过与插入排序组合，先获得一定长度的序列，然后再合并，在效率上将有所提高。

2）  当n较大，内存空间允许，且要求稳定性 =》归并排序

3）当n较小，可采用直接插入或直接选择排序。

    直接插入排序：当元素分布有序，直接插入排序将大大减少比较次数和移动记录的次数。

    直接选择排序 ：元素分布有序，如果不要求稳定性，选择直接选择排序

5）一般不使用或不直接使用传统的冒泡排序。

6）基数排序

它是一种稳定的排序算法，但有一定的局限性：

　　1、关键字可分解。

　　2、记录的关键字位数较少，如果密集更好

　　3、如果是数字时，最好是无符号的，否则将增加相应的映射复杂度，可先将其正负分开排序。

 

注明：转载请提示出处：http://blog.csdn.net/hguisu/article/details/7776068

 

 

 

感谢您的支持，我会继续努力的! 扫码打赏，你说多少就多少

         

1，有关插入排序
（1）插入排序的基本方法是：每步将一个待排序的元素，按其排序码大小插入到前面已经排好序的一组元素的适当位置上去，直到元素全部插入为止。

（2）可以选择不同的方法在已经排好序的有序数据表中寻找插入位置，依据查找方法的不同，有多种插入排序方法。下面是常用的三种。

1>直接插入排序

2>折半插入排序

3>希尔排序

（3）直接插入排序基本思想：当插入第i（i>1）个元素时，前面的data[0],data[1]……data[i-1]已经排好序。这时用data[i]的排序码与data[i-1],data[i-2],……的排序码顺序进行比较，找到插入位置即将data[i]插入，原来位置上的元素向后顺序移动。

（4）折半插入排序基本思想：设元素序列data[0],data[1],……data[n-1]。其中data[0],data[1],……data[i-1]是已经排好序的元素。在插入data[i]时，利用折半搜索法寻找data[i]的插入位置。

（5）希尔排序的过程相比前两种有些不同，下面我们主要介绍希尔排序的过程实现。
2，希尔排序##
（1）希尔排序（shell sort）这个排序方法又称为缩小增量排序，是1959年D·L·Shell提出来的。该方法的基本思想是：设待排序元素序列有n个元素，首先取一个整数increment（小于n）作为间隔将全部元素分为increment个子序列，所有距离为increment的元素放在同一个子序列中，在每一个子序列中分别实行直接插入排序。然后缩小间隔increment，重复上述子序列划分和排序工作。直到最后取increment=1，将所有元素放在同一个子序列中排序为止。

（2）由于开始时，increment的取值较大，每个子序列中的元素较少，排序速度较快，到排序后期increment取值逐渐变小，子序列中元素个数逐渐增多，但由于前面工作的基础，大多数元素已经基本有序，所以排序速度仍然很快。

（3）希尔排序举例：

1>下面给出一个数据列：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-CeZ2zOug-1571446499904)(https://img-blog.csdn.net/20180130081822620?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvd2VpeGluXzM3ODE4MDgx/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast)]

2>第一趟取increment的方法是：n/3向下取整+1=3（关于increment的取法之后会有介绍）。将整个数据列划分为间隔为3的3个子序列，然后对每一个子序列执行直接插入排序，相当于对整个序列执行了部分排序调整。图解如下：


3>第二趟将间隔increment= increment/3向下取整+1=2，将整个元素序列划分为2个间隔为2的子序列，分别进行排序。图解如下：


4>第3趟把间隔缩小为increment= increment/3向下取整+1=1，当增量为1的时候，实际上就是把整个数列作为一个子序列进行插入排序，图解如下：


5>直到increment=1时，就是对整个数列做最后一次调整，因为前面的序列调整已经使得整个序列部分有序，所以最后一次调整也变得十分轻松，这也是希尔排序性能优越的体现。

（4）希尔排序算法的代码实现（C++）
//函数功能，希尔排序算法对数字递增排序
//函数参数，数列起点，数列终点
void shell_sort(const int start, const int end) {
	int increment = end - start + 1;	//初始化划分增量
	int temp{ 0 };
	do {	//每次减小增量，直到increment = 1
		increment = increment / 3 + 1;
		for (int i = start + increment; i <= end; ++i) {	//对每个划分进行直接插入排序
			if (numbers[i - increment] > numbers[i]) {
				temp = numbers[i];
				int j = i - increment;
				do {	//移动元素并寻找位置
					numbers[j + increment] = numbers[j];
					j -= increment;
				} while (j >= start && numbers[j] > temp);
				numbers[j + increment] = temp;	//插入元素
			}
		}
	} while (increment > 1);
}

上面的函数的第一个do……while控制increment每次的缩小，其内部便是直接插入排序算法的使用，与直接插入排序算法稍有不同的一点是：其j每次的变化量是increment而不是1。

（5）关于希尔排序increment（增量）的取法。
增量increment的取法有各种方案。最初shell提出取increment=n/2向下取整，increment=increment/2向下取整，直到increment=1。但由于直到最后一步，在奇数位置的元素才会与偶数位置的元素进行比较，这样使用这个序列的效率会很低。后来Knuth提出取increment=n/3向下取整+1.还有人提出都取奇数为好，也有人提出increment互质为好。应用不同的序列会使希尔排序算法的性能有很大的差异。

（6）希尔排序应该注意的问题

从上面图解希尔排序的过程可以看到，相等的排序码25在排序前后的顺序发生了颠倒，所以希尔排序是一种不稳定的排序算法。
3，关于希尔排序的性能分析
（1）对希尔排序的时间复杂度分析很困难，在特定情况下可以准确的估算排序码的比较次数和元素移动的次数，但要想弄清楚排序码比较次数和元素移动次数与增量选择之间的依赖关系，并给出完整的数学分析，还没有人能够做到。

（2）这里我们把3种常用的插入排序做一个程序测试，通过每种算法测试所执行的时间，来定性的认识希尔排序的性能优劣。测试的思路是通过生成1000个1——1000之间的随机数，令三种排序算法分别对其进行排序，输出排序所花费的时间。

（3）测试的程序源码（C++）
/*
* 插入排序算法
*/
#include <iostream>
#include <vector>
#include <string>
#include <ctime>
using namespace std;

//vector<int> numbers{3, 2, 4, 6, 1, 9, 5, 8, 7, 10};
//vector<int> numbers{72, 6, 57, 88, 60, 42, 83, 73, 48, 85};
//vector<int> numbers{21, 25, 49, 25, 16, 8};
vector<int> numbers;

//函数功能，直接插入算法对数字排序
//函数参数，数列起点，数列终点
void dinsert_sort(const int start, const int end) {
	for (int i = start + 1; i <= end; ++i) {
		if (numbers[i] < numbers[i - 1]) {
			int temp = numbers[i];
			int j = i - 1;
			do {	//依次移动并寻找插入位置
				numbers[j + 1] = numbers[j];
				--j;
			}while (j >= start && numbers[j] > temp);
			numbers[j + 1] = temp;	//插入元素
		}
	}
}

//函数功能，折半插入算法对数字排序
//函数参数，数列起点，数列终点
void binsert_sort(const int start, const int end) {
	int low = 0, high = 0, middle = 0;
	for (int i = start + 1; i <= end; ++i) {
		int temp = numbers[i];
		low = start;
		high = i - 1;
		while (low <= high) {	//折半搜索寻找插入位置
			middle = (low + high) / 2;
			if (numbers[middle] > temp) {	
				high = middle - 1;	//定位到前半部分
			}
			else {
				low = middle + 1;	//定位到后半部分
			}
		}
		for (int k = i - 1; k >= low; --k) {
			numbers[k + 1] = numbers[k];	//成块移动，空出插入位置
		}
		numbers[low] = temp;	//插入元素
	}
}

//函数功能，希尔排序算法对数字递增排序
//函数参数，数列起点，数列终点
void shell_sort(const int start, const int end) {
	int increment = end - start + 1;	//初始化划分增量
	int temp{ 0 };
	do {	//每次减小增量，直到increment = 1
		increment = increment / 3 + 1;
		for (int i = start + increment; i <= end; ++i) {	//对每个划分进行直接插入排序
			if (numbers[i - increment] > numbers[i]) {
				temp = numbers[i];
				int j = i - increment;
				do {	//移动元素并寻找位置
					numbers[j + increment] = numbers[j];
					j -= increment;
				} while (j >= start && numbers[j] > temp);
				numbers[j + increment] = temp;	//插入元素
			}
		}
	} while (increment > 1);
}

//函数功能，随机产生amount个start——end内的随机数并存入指定容器
//函数参数，随机数范围起点，随机数范围终点，随机数生成数量
void produceRandomNumbers(const int start, const int end, const int amount) {
	srand((unsigned)time(NULL));
	for (int cnt = 1; cnt <= amount; ++cnt) {
		numbers.push_back(start + (rand() % (end - start)));
	}
}


int main()
{
	time_t c_start, c_end;
	produceRandomNumbers(1, 1000, 1000);

	c_start = clock();
	//dinsert_sort(0, 999);
	//binsert_sort(0, 999);
	shell_sort(0, 999);
	c_end = clock();

	cout << "当前排序算法花费时间为：" << difftime(c_end, c_start) << "ms" << endl;
	for (auto iter = numbers.cbegin(); iter != numbers.cend(); ++iter) {
		cout << *iter << " ";
	}

	system("pause");
	return 0;
}

（4）有关测试结果

直接插入排序：


折半插入排序：


希尔排序：


当然这里没有让其对同一组数据进行测试，会存在一定的误差，但是通过对其多次测试，3中算法的平均优劣程度还是比较明显的。

4，写在最后
关于数字的排序算法的研究是一个乐此不疲的话题，对于这些基本的排序算法应该常记、常用。也希望大家对文中不当之处给予指正。
参考资料：《数据结构C++语言描述》殷人昆/相关博文

原文链接： 冒泡排序---经典排序算法 | 逍遥游

 

冒泡排序(BubbleSort)以其“在排序过程中相邻元素不断交换，一些元素慢慢被换到最后，看起来就像是元素在冒泡一样”而得名，是一种简单的基于关键词比较的排序算法。

 

算法原理

冒泡排序的原理（以递增序为例）是每次从头开始依次比较相邻的两个元素，如果后面一个元素比前一个要大，说明顺序不对，则将它们交换，本次循环完毕之后再次从头开始扫描，直到某次扫描中没有元素交换，说明每个元素都不比它后面的元素大，至此排序完成。

由于冒泡排序简洁的特点，它通常被用来对于计算机程序设计入门的学生介绍算法的概念。

 

时间复杂度

若文件的初始状态是排好序的的，一趟扫描即可完成排序。所需的关键字比较次数C和记录移动次数 M 均达到最小值（Cmin = n-1、Mmin = 0）

所以，冒泡排序最好的时间复杂度为O(N)。


　　若初始文件是反序的，需要进行N趟排序。每趟排序要进行 C = N-1次关键字的比较(1≤i≤N-1)和总共(Mmax = (N*(N-1))/2)次的移动（移动次数由乱序对的个数决定，即多少对元素顺序不对，如 1 3 4 2 5 中共有(3,2)、(4,2)两个乱序对），在这种情况下，比较和移动次数均达到最大值（Cmax =N*(N-1) + Mmax=(N*(N-1))/2 = O(N^2)）。所以，冒泡排序的最坏时间复杂度为O(N^2)

 

综上，冒泡排序总的平均时间复杂度为O(N^2)。

算法稳定性

冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。如果两个相等的元素相邻，那么根据我们的算法。它们之间没有发生交换；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。

 

算法改进

由于冒泡排序算法还是比较慢的，所以有很多人对在此基础上进行了改进，我只简单介绍一下我所知道的。

第一种是上浮操作与下沉操作相结合。传统的冒泡排序只有上浮操作，如果碰到一些很特殊的数据就会显得笨一点，例如（2、3、4、5、1）这个数列按增序排列，那么按照普通冒泡算法就要扫描5趟，可是我们一眼就看出来直接把 1 挪到第一个就行了，扫描 5 次实在是太笨了，于是我们在每次上浮操作后加上一个下沉操作，这样就更快了。

第二中改进是减少无效比较的次数。所谓无效比较就是当我们已知结果却还要去比较。如果我们多观察冒泡排序的中间过程，我们就会发现，末尾的一些元素在一定次数的扫描后已经到达最终位置了（因为每次扫描后都至少会有一个新的元素到达最终位置），再比较就会造成无效比较。改进方法是，记录下每次扫描中发生交换的最后一个元素位置，下一次扫描就到这里为止。

可是，无论怎么改进，冒泡排序的时间复杂度都是O(N^2）。

 

下面给出冒泡排序的C++参考代码和下载地址。

 

 

//冒泡排序部分，参数形式与标准库的快排一样

//ps：(point start)所需排序的数据首地址

//pe：(point end)  所需排序的数据第一个无效地址

//cmp：自定义的比较函数

int sort(int *ps,int *pe,bool(*cmp)(int,int))

{

//用以判断某次循环后是否有元素位置发生变化

    bool flag=true;

 

    while(flag)

    {

        flag=false;//假设没有交换

 

        //上浮过程

        for(int i=1;i<pe-ps;i++)//注意：i从1开始

        {

            if(cmp(ps[i],ps[i-1]))

            {

                swap(ps[i],ps[i-1]);

                flag=true;//有元素发生交换，说明排序可能没有结束

            }

        }

    }

    return 0;

}


 

 

 

 

更详细的代码，请点击这里下载。

 

来源：逍遥游，欢迎分享本文，转载请保留出处！

假设我们现在对“6  1  2 7  9  3  4  5 10  8”这个10个数进行排序。首先在这个序列中随便找一个数作为基准数（不要被这个名词吓到了，就是一个用来参照的数，待会你就知道它用来做啥的了）。为了方便，就让第一个数6作为基准数吧。接下来，需要将这个序列中所有比基准数大的数放在6的右边，比基准数小的数放在6的左边，类似下面这种排列。

       3  1  2 5  4  6  9 7  10  8

 

        在初始状态下，数字6在序列的第1位。我们的目标是将6挪到序列中间的某个位置，假设这个位置是k。现在就需要寻找这个k，并且以第k位为分界点，左边的数都小于等于6，右边的数都大于等于6。想一想，你有办法可以做到这点吗？

 

        给你一个提示吧。请回忆一下冒泡排序，是如何通过“交换”，一步步让每个数归位的。此时你也可以通过“交换”的方法来达到目的。具体是如何一步步交换呢？怎样交换才既方便又节省时间呢？先别急着往下看，拿出笔来，在纸上画画看。我高中时第一次学习冒泡排序算法的时候，就觉得冒泡排序很浪费时间，每次都只能对相邻的两个数进行比较，这显然太不合理了。于是我就想了一个办法，后来才知道原来这就是“快速排序”，请允许我小小的自恋一下(^o^)。

 

       方法其实很简单：分别从初始序列“6  1  2 7  9  3  4  5 10  8”两端开始“探测”。先从右往左找一个小于6的数，再从左往右找一个大于6的数，然后交换他们。这里可以用两个变量i和j，分别指向序列最左边和最右边。我们为这两个变量起个好听的名字“哨兵i”和“哨兵j”。刚开始的时候让哨兵i指向序列的最左边（即i=1），指向数字6。让哨兵j指向序列的最右边（即j=10），指向数字8。





 

       首先哨兵j开始出动。因为此处设置的基准数是最左边的数，所以需要让哨兵j先出动，这一点非常重要（请自己想一想为什么）。哨兵j一步一步地向左挪动（即j--），直到找到一个小于6的数停下来。接下来哨兵i再一步一步向右挪动（即i++），直到找到一个数大于6的数停下来。最后哨兵j停在了数字5面前，哨兵i停在了数字7面前。

 



 

 

 

       现在交换哨兵i和哨兵j所指向的元素的值。交换之后的序列如下。

        6  1  2  5  9 3  4  7  10  8



 

 

 

        到此，第一次交换结束。接下来开始哨兵j继续向左挪动（再友情提醒，每次必须是哨兵j先出发）。他发现了4（比基准数6要小，满足要求）之后停了下来。哨兵i也继续向右挪动的，他发现了9（比基准数6要大，满足要求）之后停了下来。此时再次进行交换，交换之后的序列如下。

        6  1  2 5  4  3  9  7 10  8

 

        第二次交换结束，“探测”继续。哨兵j继续向左挪动，他发现了3（比基准数6要小，满足要求）之后又停了下来。哨兵i继续向右移动，糟啦！此时哨兵i和哨兵j相遇了，哨兵i和哨兵j都走到3面前。说明此时“探测”结束。我们将基准数6和3进行交换。交换之后的序列如下。

        3  1 2  5  4  6  9 7  10  8

 

 



 

 


        到此第一轮“探测”真正结束。此时以基准数6为分界点，6左边的数都小于等于6，6右边的数都大于等于6。回顾一下刚才的过程，其实哨兵j的使命就是要找小于基准数的数，而哨兵i的使命就是要找大于基准数的数，直到i和j碰头为止。

 

        OK，解释完毕。现在基准数6已经归位，它正好处在序列的第6位。此时我们已经将原来的序列，以6为分界点拆分成了两个序列，左边的序列是“3  1 2  5  4”，右边的序列是“9  7  10  8”。接下来还需要分别处理这两个序列。因为6左边和右边的序列目前都还是很混乱的。不过不要紧，我们已经掌握了方法，接下来只要模拟刚才的方法分别处理6左边和右边的序列即可。现在先来处理6左边的序列现吧。

 

        左边的序列是“3  1  2 5  4”。请将这个序列以3为基准数进行调整，使得3左边的数都小于等于3，3右边的数都大于等于3。好了开始动笔吧。

 

        如果你模拟的没有错，调整完毕之后的序列的顺序应该是。

        2  1  3  5  4

 

        OK，现在3已经归位。接下来需要处理3左边的序列“2 1”和右边的序列“5 4”。对序列“2 1”以2为基准数进行调整，处理完毕之后的序列为“1 2”，到此2已经归位。序列“1”只有一个数，也不需要进行任何处理。至此我们对序列“2 1”已全部处理完毕，得到序列是“1 2”。序列“5 4”的处理也仿照此方法，最后得到的序列如下。

        1  2  3 4  5  6 9  7  10  8

 

        对于序列“9  7  10  8”也模拟刚才的过程，直到不可拆分出新的子序列为止。最终将会得到这样的序列，如下。

        1  2  3 4  5  6  7  8 9  10

 

        到此，排序完全结束。细心的同学可能已经发现，快速排序的每一轮处理其实就是将这一轮的基准数归位，直到所有的数都归位为止，排序就结束了。下面上个霸气的图来描述下整个算法的处理过程。


 

 

        快速排序之所比较快，因为相比冒泡排序，每次交换是跳跃式的。每次排序的时候设置一个基准点，将小于等于基准点的数全部放到基准点的左边，将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换，交换的距离就大的多了。因此总的比较和交换次数就少了，速度自然就提高了。当然在最坏的情况下，仍可能是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和冒泡排序是一样的都是O(N2)，它的平均时间复杂度为O(NlogN)。


#include <stdio.h>
int a[101],n;//定义全局变量，这两个变量需要在子函数中使用
void quicksort(int left, int right) {
	int i, j, t, temp;
	if(left > right)
		return;
    temp = a[left]; //temp中存的就是基准数
    i = left;
    j = right;
    while(i != j) { //顺序很重要，要先从右边开始找
    	while(a[j] >= temp && i < j)
    		j--;
    	while(a[i] <= temp && i < j)//再找右边的
    		i++;       
    	if(i < j)//交换两个数在数组中的位置
    	{
    		t = a[i];
    		a[i] = a[j];
    		a[j] = t;
    	}
    }
    //最终将基准数归位
    a[left] = a[i];
    a[i] = temp;
    quicksort(left, i-1);//继续处理左边的，这里是一个递归的过程
    quicksort(i+1, right);//继续处理右边的 ，这里是一个递归的过程
}
int main() {
	int i;
    //读入数据
	scanf("%d", &n);
	for(i = 1; i <= n; i++)
		scanf("%d", &a[i]);
    quicksort(1, n); //快速排序调用
    //输出排序后的结果
    for(i = 1; i < n; i++)
    	printf("%d ", a[i]);
    printf("%d\n", a[n]);
    return 0;
}