快速排序 其思想是：先选一个“标尺”， 用它把整个队列过一遍筛子， 以保证：其左边的元素都不大于它，其右边的元素都不小于它。 这样，排序问题就被分割为两个子区间。 再分别对子区间排序就可以了。
选择排序 思想：重复选择数组内的最大值，交换到合适的位置。该排序方法比较慢。
堆排序 思想：堆实际上是一棵完全二叉树，利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性，使得每次从无序中选择最大记录(最小记录)。堆排序其实也是一种选择排序，是一种树形选择排序。
归并排序 思想：这是一个采用分治法的算法，先使每个子序列有序，再使子序列段间有序，再将已有序的子序列合并，这样就能得到完全有序的序列。桶排序代码一起上
#include <cstdio>#include <cstring>#include <cstdlib>#include <conio.h>#include <cmath>#include <iostream>#define MAXSIZE 120#define FALSE 0#define TRUE 1using namespace std;typedef struct{ int r[MAXSIZE + 1]; int length;} SqList;typedef int RedType;int CompareCount;//随意数据的生成void SortInit(SqList *L){ int i, j, temp; L->r[1] = (rand() % 1000); for (i = 2; i <= MAXSIZE; i++) { do { temp = (rand() % 1000); for (j = 1; j < i; j++) if (temp == L->r[j]) break; } while (j < i); L->r[i] = temp; } L->length = MAXSIZE;}//数据拷贝void DataCopy(SqList L, SqList &L1){ L1.length = L.length; for (int i = 1; i <= L.length; i++) L1.r[i] = L.r[i];}//直接插入排序void InsertSort(SqList &L){ int i, j; CompareCount = 0; for (i = 2; i <= L.length; i++) { CompareCount++; if (L.r[i] < L.r[i - 1]) { L.r[0] = L.r[i]; for (j = i - 1; L.r[0] < L.r[j]; j--) { L.r[j + 1] = L.r[j]; CompareCount++; } L.r[j + 1] = L.r[0]; } }}//希尔排序void ShellInsert(SqList &L, int dk){ int j; for(int i = dk +1 ;i<=L.length;i++){ CompareCount++; if(L.r[i]<L.r[i-dk]){ L.r[0]=L.r[i]; for( j = i-dk; j>0&&L.r[0]<L.r[j];j-=dk){ L.r[j+dk] = L.r[j]; CompareCount++; } L.r[j+dk] = L.r[0]; } } return;}void ShellSort(SqList &L ){ CompareCount = 0; for(int d = L.length/2; d > 0; d/=2){ ShellInsert(L,d); } return;}//冒泡排序void BubbleSort(SqList &L){ CompareCount = 0; int t, flag=1; int m = L.length-1; while(m>0&&flag==1){ flag = 0; CompareCount++; for(int j=1;j<=m;j++){ CompareCount++; if(L.r[j]>L.r[j+1]){ flag =1; t= L.r[j]; L.r[j]= L.r[j+1]; L.r[j+1]=t; } } m--; }}//快排int Partition(SqList &L, int low, int high){ int pivot; L.r[0] = L.r[low]; pivot = L.r[low]; while(low<high){ CompareCount++; while(low < high&&L.r[high]>=pivot){ CompareCount++; high--; } L.r[low] = L.r[high]; while(low < high&&L.r[low]<= pivot){ CompareCount++; low++; } L.r[low]= L.r[0]; return low; }}void QuickSort(SqList &L, int low, int high){ int pivotloc; if (low <high){ pivotloc = Partition(L,low,high); QuickSort(L,low,pivotloc-1); QuickSort(L,pivotloc+1,high); } return;}void QSort(SqList &L){ CompareCount = 0; QuickSort(L,1,L.length);}//直接选择排序void SelectSort(SqList &L) //直接选择排序{ CompareCount = 0; int temp; int i,j,k; for (i=1; i<L.length; ++i)//在L.r[i..L.length] 中选择key最小的记录 { CompareCount++; k=i; for( j=i+1;j<=L.length ; j++){ //查找最小的元素 CompareCount++; if ( L.r[j] <L.r[k]){ k=j; } } if(k!=i) { temp=L.r[i]; L.r[i]=L.r[k]; L.r[k]=temp; } }}//堆排序void HeapAdjust(SqList &L, int s, int m)// 算法10.10{ // 已知H.r[s..m]中记录的关键字除H.r[s].key之外均满足堆的定义，本函数 // 调整H.r[s]的关键字，使H.r[s..m]成为一个大顶堆(对其中记录的关键字而言) RedType rc; int j; rc=L.r[s]; for(j=2*s;j<=m;j*=2) { // 沿key较大的孩子结点向下筛选 CompareCount++; if(j<m&&L.r[j]<L.r[j+1]){ ++j; // j为key较大的记录的下标 } if(rc>L.r[j]) break; // rc应插入在位置s上 L.r[s]=L.r[j]; s=j; } L.r[s]=rc; // 插入}void HeapSort(SqList &L){ // 对顺序表H进行堆排序。算法10.11 RedType t; int i; CompareCount = 0; for(i=L.length/2;i>0;--i) {// 把H.r[1..H.length]建成大顶堆 HeapAdjust(L,i,L.length); CompareCount++; } for(i=L.length;i>1;--i) { // 将堆顶记录和当前未经排序子序列H.r[1..i]中最后一个记录相互交换 t=L.r[1]; L.r[1]=L.r[i]; L.r[i]=t; CompareCount++; HeapAdjust(L,1,i-1); // 将H.r[1..i-1]重新调整为大顶堆 }}//归并排序void Merge(RedType SR[],RedType TR[],int i,int m,int n){ // 将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n] 算法10.12 int j,k,l; for(j=m+1,k=i;i<=m&&j<=n;++k) // 将SR中记录由小到大地并入TR { CompareCount++; if(SR[i] <= SR[j]){ TR[k]=SR[i++]; } else{ TR[k]=SR[j++]; } } if(i<=m) for(l=0;l<=m-i;l++){ CompareCount++; TR[k+l]=SR[i+l]; // 将剩余的SR[i..m]复制到TR } if(j<=n) for(l=0;l<=n-j;l++){ CompareCount++; TR[k+l]=SR[j+l]; // 将剩余的SR[j..n]复制到TR }}void MSort(RedType SR[],RedType TR1[],int s, int t){ // 将SR[s..t]归并排序为TR1[s..t]。算法10.13 int m; RedType TR2[MAXSIZE+1]; if(s==t) TR1[s]=SR[s]; else { m=(s+t)/2; // 将SR[s..t]平分为SR[s..m]和SR[m+1..t] MSort(SR,TR2,s,m); // 递归地将SR[s..m]归并为有序的TR2[s..m] MSort(SR,TR2,m+1,t); // 递归地将SR[m+1..t]归并为有序的TR2[m+1..t] Merge(TR2,TR1,s,m,t); // 将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t] }}void MergeSort(SqList &L){ // 对顺序表L作归并排序。算法10.14 CompareCount = 0; MSort(L.r,L.r,1,L.length);}//输出排序结果void OutputSortData(SqList L){ int i; for (i = 1; i <= MAXSIZE; i++) { if ((i - 1) % 10 == 0) PRintf("/n"); printf("%6d", L.r[i]); } getchar(); cout <<endl;}//进行7种排序并输出结果void sort(SqList L, SqList &L1, int a[20][2], int No){ cout <<"初始化的数据为："<<endl; OutputSortData(L); //直接插入排序 cout <<"直接插入排序"<<endl; DataCopy(L, L1); InsertSort(L1); a[1][No] = CompareCount; OutputSortData(L1); //希尔排序 cout <<"希尔排序"<<endl; DataCopy(L, L1); ShellSort(L1); a[2][No] = CompareCount; OutputSortData(L1); //冒泡排序 cout <<"冒泡排序"<<endl; DataCopy(L, L1); BubbleSort(L1); a[3][No] = CompareCount; OutputSortData(L1); //快速排序 cout <<"快速排序"<<endl; DataCopy(L, L1); CompareCount = 0; QSort(L1); a[4][No] = CompareCount; OutputSortData(L1); //直接选择排序 cout <<"直接选择排序"<<endl; DataCopy(L, L1); SelectSort(L1); a[5][No] = CompareCount; OutputSortData(L1); //堆排序 cout <<"堆排序"<<endl; DataCopy(L, L1); HeapSort(L1); a[6][No] = CompareCount; OutputSortData(L1); //归并排序 cout <<"归并排序"<<endl; DataCopy(L, L1); MergeSort(L1); a[7][No] = CompareCount; OutputSortData(L1);}int main(){ int i, a[20][2]; char SortName[][15] = {"", "直接插入排序", "希尔排序", "冒泡排序", "快速排序", "直接选择排序", "堆排序","归并排序"}; SqList L, L1, L2, L3; SortInit(&L); printf("（一）排序的结果为：/n"); sort(L, L1, a, 0); printf("（二）各排序的比较次数为：/n"); for (int i = 1; i <= 7; i++) { cout << SortName[i] << endl; printf("%d/n", a[i][0]); cout << endl; } system("pause"); return 0;}新闻热点
疑难解答
