各种排序算法总结

排序的基本概念

快速记忆不稳定排序有哪些：快（快速排序）些（希尔排序）选（选择排序）一堆（堆排序）美女

返回顶部

冒泡排序（Bubble Sort）

思想： 两两比较相邻关键字，及时交换。
*过程：*** 每一趟沉淀一个最大的数。整个过程就像水泡的浮起过程，故因此而得名。
*实现代码：***

void BubbleSort1(int a[],int n){//冒泡排序 
	for(int i=0;i<n-1;i++){
		for(int j=0;j<n-1-i;j++){
			if(a[j]>a[j+1]){
				swap(a[j],a[j+1]);
			}
		}
	}
}

运行结果：
上述代码有一点问题，就是如果某一趟没有发生任何关键字的交换（说明关键字已经有序了），这时就不在需要再继续去比较了。

改进后的冒泡排序：

void BubbleSort2(int a[],int n){//改进的冒泡排序 
	int bound,exchange=n-1;
	while(exchange!=0){
		bound=exchange;
		exchange=0;
		for(int j=0;j<bound;j++){			
			if(a[j]>a[j+1]){
				swap(a[j],a[j+1]);
				exchange=j;
			}
		}
	}
}  

运行结果：
算法分析：
最好情况（正序）：
只需一趟排序，比较n-1次且不移动记录。

最坏情况（逆序）：
需n-1趟排序。每一趟比较n-1,n-2,…1次,等差数列，每次交换移动3次记录。
总的比较次数 KCN=n(n-1)/ 2
总的移动次数 RMN=3n(n-1)/ 2

平均情况下：
比较次数： (n-1)(n+2)/4 ,约为 n^2^/4
移动次数： 3n(n-1)/4,约为 3n^2^/4

时间复杂度：O(n^2^)
空间复杂度： O(1)

算法特点：

• 是稳定排序
• 可用于链式存储结构
• 当初始记录无序，n比较大时，此算法不宜采用。

返回顶部

快速排序（Quick Sort）

思想： 选取一个关键字作为分界点，右边的值都比它大，左边值都比它小。左右的 数据可以独立的排序。这是一个递归定义。
*过程：*** 每一趟将数据分为两部分，左小右大，直至low==high。
*实现代码：***

int Partition(int a[],int low,int high){	
	int pivokey=a[low];
	while(low < high) {
		while(a[high]>=pivokey&&low < high)  high--;	//直到找到一个小的 
		a[low]=a[high];			//正是因为选取第一个元素为基准，才能这样，要不然值都被覆盖了 
		while(a[low]<=pivokey&&low < high)  low++;		//直到找到一个大的 
		a[high]=a[low]; 	
	}  

	a[low]=pivokey;
	return low;
}

void QuickSort(int r[],int low,int high){
	int pivot;
	if(low<high){
		pivot=Partition(r,low,high);
		QuickSort(r,low,pivot-1);
		QuickSort(r,pivot+1,high);
	}
}

运行结果：

上述代码有一点问题，就是选取第一个或者最后一个元素作为基准，这样在数组已经有序的情况下，每次划分将得到最坏的结果。
一种比较常见的优化方法是随机化算法，即随机选取一个元素作为基准。这种情况下最坏情况不再依赖于输入数据，而是由随机函数决定。实际上，随机化快速排序得到理论最坏情况的可能性仅为 1/(2n)。

改进后的快速排序：

void QuickSort(int array[],int low,int high){
	srand(unsigned(time(0)));
    int sc=rand()%(high-low)+1+low;
    cout<<"随机数"<<sc<<endl;
    swap(array[sc],array[low]);
    show(array,11);
    int par=Partition(array,low,high);
    if (par>low+1){
        QuickSort(array,low,par-1);
    }
    if (par<high-1){
        QuickSort(array,par+1,high);
    }
}

运行结果：

算法分析：
最好情况：
每一次分割都是长度大致相等的子表

最坏情况（有序）：
每一次分割只能得到比上一次记录少一个的子序列。

平均时间复杂度：O(nlog2n)
空间复杂度： 最好O(log2n)、最差O(n)

算法特点：

• 是不稳定排序
• 很难于链式存储结构
• 当初始记录无序，n比较大时，此算法宜采用。

返回顶部

直接插入排序（Straight Insertion Sort）

思想： 与怕扑克牌一样，拿起一张牌，插入合适位置。
*过程：*** 每一趟将一个待排序记录插入到适当位置。
*实现代码：***

void InsertSort(int r[],int n){//第0位置设置观察哨，第1位置为有序区，从第二个开始扫描插入 
	int i,j;
	for(i=2;i<=n;i++){
		r[0]=r[i];
		for(j=i-1;r[0]<r[j];j--){//带插入的数依次和有序区比，寻找插入位置 
			r[j+1]=r[j];

		}
		
		r[j+1]=r[0];
	}
}

运行结果：
红线左边的是作为观察哨用的，也就是数组中第0位置被设为观察哨。

算法分析：
最好情况（正序）：
每一趟排序，比较1次且不移动。

最坏情况（逆序）：
每一趟排序。比较i次，移动i+1次。

整个过程（需执行n-1趟）：
最好情况，比较n-1次且不移动记录。
最坏情况，每一趟比较2,3,…,n,等差数列。移动3,4,…n+1次，等差数列。
总的比较次数 KCN=(n-1)(n+2)/ 2
总的移动次数 RMN=(n+4)(n-1)/ 2

平均情况下：
比较次数： (n-1)(n+4)/4 ,约为 n^2^/4
移动次数： (n+4)(n-1)/4,约为 n^2^/4
时间复杂度：O(n^2^)
空间复杂度： O(1)

算法特点：

• 是稳定排序
• 可用于链式存储结构
• 当初始记录无序，n比较大时，此算法不宜采用。

返回顶部

折半插入排序（Binary Insertion Sort）

与直接插入排序区别不大，直接插入排序是以顺序查找方式找插入位置，这里只是将其换为折半查找方式来找插入位置。

实现代码：

void BInsertSort(int Array[],int n)		// 折半插入排序升序排列
{
	int i,j,m;      //m充当比较区间的中点
	int low,high;     
	for (i = 2; i <= n; i++)
	{
		Array[0] = Array[i];
		low = 1; high = i-1;   
	
		while (low <= high){
			m = (low + high)/2;
			if (Array[0] > Array[m])  low = m+1;
			else  high = m-1;
		}
		/*确定好位置后，将位置之后的数据后移，插入待排序数据*/
		for (j = i-1;j > high; j--){
			Array[j+1] = Array[j];
		}
		Array[j+1] = Array[0];
	}
}

运行结果与直接插入排序一样

算法分析：
平均情况下，折半查找比顺序查找快，但移动次数不变。

时间复杂度：O(n^2^)
空间复杂度： O(1)

算法特点：

• 是稳定排序
• 不可用于链式存储结构
• 适合初始记录无序，n比较大时。

返回顶部

希尔排序（Shell’s Sort）

思想： 通过 增量 将整个待排序列分割成几组，对每组分别进行直接插入排序。然后改变增量，重新分组，增加每组的数据量。直到所取增量为1，所有记录在同一组中进行直接插入排序。
*过程：*** 每一趟分组排序，使得整个待排序列趋于 *“基本有序”。*** 最后在一个组中直接插入排序的时候效率高。

实现代码：

void ShellInsertSort(int a[], int n)			//希尔排序 
{ 
    int d, i, j; //d为增量
    for(d = n/2;d >= 1;d = d/2){ //增量递减到1使完成排序  
        
		for(i = d; i < n;i++){   //插入排序的一轮       
            a[0] = a[i];
            for(j = i - d;(j >= 0) && (a[j] > a[0]);j = j-d){
                a[j + d] = a[j];
            }
        	a[j + d] = a[0];
        }
    }
}

运行结果：

算法分析：
增量大于1时，关键字是跳跃移动的，最后一趟只需做少量比较和移动即可完成排序。

时间复杂度：O(n^1.3^)
空间复杂度： O(1)

算法特点：

• 是不稳定排序
• 不可用于链式存储结构
• 适合初始记录无序，n比较大时。

返回顶部

简单选择排序（Simple Selection Sort）

也叫直接选择排序

思想： 每一趟选择待排记录中关键字最小的记录。
*过程：*** 经过n-1趟，排序完成。
*实现代码：***

void SelectionSort(int a[], int n) {	//直接选择排序 
    int i,j,pos;
	for(i=0;i<n-1;i++){
        for (pos=i, j=i+1; j<n; j++)
            if (a[pos]>a[j])
                pos=j;
        if (pos != i) {
            swap(a[i],a[pos]);
        }
    }
}

运行结果：
算法分析：
最好情况（正序）：不移动记录。
最坏情况（逆序）：移动3(n-1)次记录。

无论如何，比较次数均为： KCN=n(n-1)/ 2

时间复杂度：O(n^2^)
空间复杂度： O(1)

算法特点：

• 是不稳定排序
• 可用于链式存储结构
• 适用于每一记录占用空间较多，移动次数较少。

返回顶部

堆排序（Heap Sort）

---

什么是堆：
n个元素的序列{k1，k2，…，kn}，满足：
*ki>=k2i 且 ki>=k2i+1***
或 *ki<=k2i 且 ki<=k2i+1***
称之为 堆

---

将待排数组记录看成是一棵完全二叉树的顺序存储结构，则堆实质上是满足如下性质的完全二叉树：

树中所有非终端结点的值均不大于（或不小于）其左右孩子结点的值

对应大根堆与小根堆。

---

思想： 利用大根堆（或小根堆）堆顶记录的关键字最大（或最小）这一特征，每次都选择堆的堆顶。
**过程：** 每拿走一个堆顶（把堆顶记录与最后一个记录交换），重新调整为堆，继续拿。

实现代码：
调整堆：

void heapAdjust(int a[], int i, int nLength) 	//调整堆
{
	/*2*i+1与2*i+2为i的孩子，是因为数组从0位置开始存。
	如果0位置不用，那就是2*i与2*i+1为i的孩子*/ 
    int child;		 
    for (; 2 * i + 1 < nLength; i = child)
    { 
        child = 2 * i + 1;
        
        if ( child < nLength-1 && a[child + 1] > a[child])	// 得到子结点中较大的结点
            ++child;
        
        if (a[i] < a[child]){		// 如果较大的子结点大于父结点,交换 
        	swap(a[i],a[child]);
        }
        else  break;
    }
}

建初堆：
在完全二叉树中，所有序号大于⌊n/2⌋ 的结点都是叶子，以这些结点为根的子树已是堆，不用调整。

void CreatHeap(int a[],int n){				//建初堆
	for (int i = n / 2 - 1; i >= 0; --i)	//length/2-1是第一个非叶节点
        heapAdjust(a, i, n);
        show(a,11); 
}

堆排序：

void HeapSort(int a[],int length)	// 堆排序
{
	cout<<"初始大根堆如下："<<endl;
    CreatHeap(a,length);			//把无序序列变成大根堆
	 
    // 从最后一个元素开始对序列进行调整
    for (int i = length - 1; i > 0; --i)
    {    
      	swap(a[i],a[0]);			// 把第一个元素和当前的最后一个元素交换，       
        heapAdjust(a, 0, i);		//不断的缩小调整的范围直到第一个元素     
		cout<<"后续调整堆如下："<<endl;
		show(a,11); 
    }
}

运行结果：
算法分析：

时间复杂度：O(nlog2n)
空间复杂度： O(1)

算法特点：

• 是不稳定排序
• 不可用于链式存储结构
• 数据较多时较为高效。

返回顶部

归并排序（Merging Sort）

思想： 将两个或两个以上的有序表合并成一个有序表。
**过程：** 初始序列可看成是n个有序的子序列，每个字序列长度为1，然后两两归并，重复，直到得到长度为n的有序序列为止。

实现代码：

void Merge(int r[],int r1[],int s,int m,int t){//归并 
	int i=s,j=m+1,k=s;
	while(i<=m&&j<=t){
		if(r[i]<r[j]) r1[k++]=r[i++];
		else r1[k++]=r[j++];
	}
	while(i<=m){
		r1[k++]=r[i++];
	}
	while(j<=t){
		r1[k++]=r[j++];
	}
}

void MergeSort(int r[],int s,int t){
	int m,r1[t];
	if(s==t) return;
	else{
		m=(s+t)/2;						//分割序列
		MergeSort(r,s,m);				//递归
		MergeSort(r,m+1,t);
		Merge(r,r1,s,m,t);				//归并
		for(int i=s;i<=t;i++){			//将排好序的部分写回原数组
			r[i]=r1[i];
		}			
	}
}

运行结果：

算法分析：

时间复杂度：O(nlog2n)
空间复杂度： O(n)

算法特点：

• 是稳定排序
• 可用于链式存储结构

返回顶部

基数排序（Radix Sort）

它是和前面所述各类排序方法完全不同的一种排序方法。前面的各类排序方法都是建立在关键字比较的基础上的，而基数排序不比较关键字的大小，是一种借助于多关键字排序的思想对单关键字排序的方法。

怎么理解呢？
以扑克牌为例，扑克牌由面值和花色构成（多关键字），要对这副牌进行排序有两种策略（**以花色大于面值，且红桃>黑桃>梅话>方块来说明**）：

1. 最高位优先法（MSD（Most significant digital））
   先将牌按花色分为四堆，然后每一堆按面值进行排序。
   
   
   
   这样，这副牌就按从小到大顺序排好了。

2. 最低位优先法（LSD（Least significant digital））
   这是一种“分配”与“收集”交替进行的方法。
   先将牌按面值分成13堆（完整的牌），从小到大收集起来，再把花色一样的放在一起即可。
   
   
   
   这样，这副牌就按从小到大顺序排好了。

基数排序思想： 一个关键字可以看成是“多个关键字”组成，个位、十位、百位等，从而借助于多关键字排序对单关键字排序。
*过程：*** 从低位到高位，将值相同的收集起来放在一个队里。再分配，再收集，最终完成排序
*实现代码：***

int getNumInPos(int num,int pos) //获得某个数字的第pos位的值
{
    int temp = 1;
    for (int i = 0; i < pos - 1; i++)
        temp *= 10;
 
    return (num / temp) % 10;
}
 
#define RADIX 10    //可能是0-9，需要10个桶 
#define KEYNUM 5     //整数位数
void RadixSort(int a[], int n)		//基数排序 
{
    int *radixArrays[RADIX];    //分别为0~9的序列空间
    for (int i = 0; i < RADIX; i++)
    {
        radixArrays[i] = new int[n];
        radixArrays[i][0] = 0;    
    }
 
    for (int pos = 1; pos <= KEYNUM; pos++)    //从个位开始
    {
        for (int i = 0; i < n; i++)    //分配过程
        {
            int num = getNumInPos(a[i], pos);
            int index = ++radixArrays[num][0];
            radixArrays[num][index] = a[i];
        }
 
        for (int i = 0, j =0; i < RADIX; i++) //写回到原数组中
        {
            for (int k = 1; k <= radixArrays[i][0]; k++)
                a[j++] = radixArrays[i][k];
            radixArrays[i][0] = 0;
        }
    }
}

运行结果：

算法分析：
对于n个记录，假设每个记录含d个关键字，每个关键字的取值范围为rd个值，每一趟分配的时间复杂度为 O(n) ，每一趟收集的时间复杂度为 O(rd) 。整个排序需进行d趟分配与收集。
*时间复杂度：O(d(n+rd))***
*空间复杂度： O(n+rd)***

算法特点：

• 是稳定排序
• 可用于链式存储结构
• 时间复杂度能突破基于关键字比较方法的下界 O(nlog2n)。 达到 O(n)。

返回顶部

总的代码：

#include<iostream>
#include <stdlib.h>
#include <ctime>
using namespace std;

void swap(int &a,int &b){
	int temp=a;a=b;b=temp;
}

void show(int a[],int n){
	for(int i=0;i<n;i++){
		cout<<a[i]<<" ";
	}
	printf("\n");
}

void BubbleSort1(int a[],int n){//冒泡排序
	show(a,n); 
	for(int i=0;i<n-1;i++){
		for(int j=0;j<n-1-i;j++){
			if(a[j]>a[j+1]){
				swap(a[j],a[j+1]);				
			}
		}
		cout<<"第"<<i+1<<"趟比较结果："<<endl;
		show(a,n);
	}
}

void BubbleSort2(int a[],int n){//改进的冒泡排序 
	show(a,n); 
	int bound,exchange=n-1;
	int i=0;
	while(exchange!=0){
		cout<<"第"<<++i<<"趟比较结果："<<endl;
			show(a,n);
		bound=exchange;
		exchange=0;
		for(int j=0;j<bound;j++){			
			if(a[j]>a[j+1]){
				swap(a[j],a[j+1]);
				exchange=j;
			}
		}
	}
}  

void quicksort(int a[],int low,int high){//快速排序 
 
	if(low>high) return;
	int pivokey=a[low];
	int left=low;
	int right=high;
	while(left<right) {
		while(a[right]>=pivokey&&left<right)  right--;		//直到找到一个小的 
		while(a[left]<=pivokey&&left<right)  left++;		//直到找到一个大的 
		if(left<right)  swap(a[left],a[right]); 		
	}  	
	a[low]=a[left];			//正是因为选取第一个元素为基准，才能这样，要不然值都被覆盖了 
	a[left]=pivokey;
	
	quicksort(a,low,left-1);
	quicksort(a,left+1,high);
}

//int Partition(int r[],int low,int high){
//	int i=low,j=high;
//	while(i<j){
//		while(i<j&&r[i]<=r[j]) j--;			//直到找到一个小的 
//		if(i<j){
//			cout<<r[i]<<"和"<<r[j]<<"交换"<<endl;
//			swap(r[i],r[j]);
//			//i++;
//		}
//		while(i<j&&r[i]<=r[j]) i++;			//直到找到一个大的 
//		if(i<j){
//			cout<<r[i]<<"和"<<r[j]<<"交换"<<endl;
//			swap(r[i],r[j]);
//			//j--;
//		}
//		show(r,11);
//	}
//	cout<<endl<<"位置"<<i<<endl<<endl;
//	return i;
//}

int Partition(int a[],int low,int high){	
	int pivokey=a[low];
	while(low < high) {
		while(a[high]>=pivokey&&low < high)  high--;	//直到找到一个小的 
		a[low]=a[high];			//正是因为选取第一个元素为基准，才能这样，要不然值都被覆盖了 
		while(a[low]<=pivokey&&low < high)  low++;		//直到找到一个大的 
		a[high]=a[low]; 	
	
	}  
	a[low]=pivokey;
	return low;
}

//void QuickSort(int r[],int low,int high){
//	int pivot;
//	if(low<high){
//		pivot=Partition(r,low,high);
//		QuickSort(r,low,pivot-1);
//		QuickSort(r,pivot+1,high);
//	}
//}

void QuickSort(int array[],int low,int high){//随机化法改进的快速排序 
	srand(unsigned(time(0)));
    int sc=rand()%(high-low)+1+low;
    cout<<"随机数"<<sc<<endl;
    swap(array[sc],array[low]);
    int par=Partition(array,low,high);
    if (par>low+1){
        QuickSort(array,low,par-1);
    }
    if (par<high-1){
        QuickSort(array,par+1,high);
    }
}

int SelectMink(int r[],int low,int high,int k){ 
	int s= Partition(r,low,high);
	if(s==k) return r[s];
	if(s>k) return SelectMink(r,low,s-1,k);
	else return SelectMink(r,s+1,high,k);
}

void InsertSort(int r[],int n){//第0位置设置观察哨，第1位置为有序区，从第二个开始扫描插入 
	int i,j;
	for(i=2;i<=n;i++){
		r[0]=r[i];
		for(j=i-1;r[0]<r[j];j--){//带插入的数依次和有序区比，寻找插入位置 
			r[j+1]=r[j];

		}
		
		r[j+1]=r[0];
		cout<<"第"<<i-1<<"趟结果："<<endl;
		show(r,11);
	}
}

void BInsertSort(int Array[],int n)		//第0位置设置观察哨，折半插入排序升序排列
{
	int i,j,m;      //m充当比较区间的中点
	int low,high;     
	for (i = 2; i <= n; i++)
	{
		Array[0] = Array[i];
		low = 1; high = i-1;   
	
		while (low <= high){
			m = (low + high)/2;
			if (Array[0] > Array[m])  low = m+1;
			else  high = m-1;
		}
		/*确定好位置后，将位置之后的数据后移，插入待排序数据*/
		for (j = i-1;j > high; j--){
			Array[j+1] = Array[j];
		}
		Array[j+1] = Array[0];
		cout<<"第"<<i-1<<"趟结果："<<endl;
		show(Array,11);
	}
}

void ShellInsertSort(int a[], int n)			//希尔排序 
{ 
    int d, i, j; //d为增量
    for(d = n/2;d >= 1;d = d/2){ //增量递减到1使完成排序  
        
		for(i = d; i < n;i++){   //插入排序的一轮       
            a[0] = a[i];
            for(j = i - d;(j >= 0) && (a[j] > a[0]);j = j-d){
                a[j + d] = a[j];
            }
        	a[j + d] = a[0];
        }
    }
}

void SelectionSort(int a[], int n) {	//直接选择排序 
    int i,j,pos;
	for(i=0;i<n-1;i++){
        for (pos=i, j=i+1; j<n; j++)
            if (a[pos]>a[j])
                pos=j;
        if (pos != i) {
            swap(a[i],a[pos]);
        }
        cout<<"第"<<i+1<<"趟结果："<<endl;
		show(a,n);
    }
}

void heapAdjust(int a[], int i, int nLength)
{
	/*2*i+1与2*i+2为i的孩子，是因为数组从0位置开始存。
	如果0位置不用，那就是2*i与2*i+1为i的孩子*/ 
    int child;		 
    for (; 2 * i + 1 < nLength; i = child)
    { 
        child = 2 * i + 1;
        
        if ( child < nLength-1 && a[child + 1] > a[child])	// 得到子结点中较大的结点
            ++child;
        
        if (a[i] < a[child]){		// 如果较大的子结点大于父结点,交换 
        	swap(a[i],a[child]);
        }
        else  break;
    }
}

void CreatHeap(int a[],int n){
	for (int i = n / 2 - 1; i >= 0; --i)	//length/2-1是第一个非叶节点
        heapAdjust(a, i, n);
        show(a,11); 
}

void HeapSort(int a[],int length)	// 堆排序
{
	cout<<"初始大根堆如下："<<endl;
    CreatHeap(a,length);			//把无序序列变成大根堆
	 
    // 从最后一个元素开始对序列进行调整
    for (int i = length - 1; i > 0; --i)
    {    
      	swap(a[i],a[0]);			// 把第一个元素和当前的最后一个元素交换，       
        heapAdjust(a, 0, i);		//不断的缩小调整的范围直到第一个元素     
		cout<<"后续调整堆如下："<<endl;
		show(a,11); 
    }
}

void Merge(int r[],int r1[],int s,int m,int t){//归并 
	int i=s,j=m+1,k=s;
	while(i<=m&&j<=t){
		if(r[i]<r[j]) r1[k++]=r[i++];
		else r1[k++]=r[j++];
	}
	while(i<=m){
		r1[k++]=r[i++];
	}
	while(j<=t){
		r1[k++]=r[j++];
	}
}

void MergeSort(int r[],int s,int t){
	int m,r1[t];
	if(s==t) return;
	else{
		m=(s+t)/2;
		MergeSort(r,s,m);
		MergeSort(r,m+1,t);
		Merge(r,r1,s,m,t);
		cout<<s<<"->"<<t<<"位置已排好序"<<endl;
		for(int i=s;i<=t;i++){
			r[i]=r1[i];
		}
		show(r,11);			
	}
}

int getNumInPos(int num,int pos) //获得某个数字的第pos位的值
{
    int temp = 1;
    for (int i = 0; i < pos - 1; i++)
        temp *= 10;
 
    return (num / temp) % 10;
}
 
#define RADIX 10    //可能是0-9，需要10个桶 
#define KEYNUM 5     //整数位数
void RadixSort(int a[], int n)		//基数排序 
{
    int *radixArrays[RADIX];    //分别为0~9的序列空间
    for (int i = 0; i < RADIX; i++)
    {
        radixArrays[i] = new int[n];
        radixArrays[i][0] = 0;    
    }
 
    for (int pos = 1; pos <= KEYNUM; pos++)    //从个位开始
    {
        for (int i = 0; i < n; i++)    //分配过程
        {
            int num = getNumInPos(a[i], pos);
            int index = ++radixArrays[num][0];
            radixArrays[num][index] = a[i];
        }
 
        for (int i = 0, j =0; i < RADIX; i++) //写回到原数组中
        {
            for (int k = 1; k <= radixArrays[i][0]; k++)
                a[j++] = radixArrays[i][k];
            radixArrays[i][0] = 0;
        }
    }
}


int main(){
  	int n=11;
    int a[n]={5,3,8,1,4,6,9,2,7,10,11};
//    srand(unsigned(time(0)));
//    for (int i = 0; i <n ; i++) {
//        a[i] = rand()%100+1;
//    }

//	cout<<"直接插入排序:"<<endl;
//	show(a,n);
//	InsertSort(a,n-1); 
//	show(a,n);

//	cout<<"折半插入排序:"<<endl;
//	show(a,n);
//	BInsertSort(a,n-1); 
//	show(a,n);

//	cout<<"希尔排序:"<<endl;
//	show(a,n);
//	ShellInsertSort(a,n-1); 
//	show(a,n);

//	cout<<"快速排序:"<<endl;
//	show(a,n);
//    QuickSort(a,0,n-1);
//	quicksort(a,0,n-1);
//	show(a,n);

//	cout<<endl<<"冒泡排序:"<<endl;
//	BubbleSort1(a,n);
//	show(a,n);
//	
//	cout<<endl<<"改进的冒泡排序:"<<endl;
//	BubbleSort2(a,n);
//	show(a,n);
	
//	cout<<endl<<"直接选择排序:"<<endl;
//	show(a,n);
//	SelectionSort(a,n);
//	show(a,n);
	
//	cout<<"堆排序:"<<endl;
//	show(a,n);
//	HeapSort(a,n);
//	show(a,n);

//    cout<<endl<<"归并排序:"<<endl;
//    show(a,n);
//    MergeSort(a,0,n-1);
//   	show(a,n);
   	
//   	cout<<endl<<"基数排序:"<<endl;
//    show(a,n);
//    RadixSort(a,n);
//   	show(a,n);
   	
    int choose;
    show(a,n);
    cout<<"请输入要查询第几小的数:"<<endl; 
    cin>>choose; 
    printf("第%d小的数是：%d\n",choose,SelectMink(a,0,n,choose));
	
	return 0;
}

返回顶部