常用排序模板

2019-11-06 06:24:12

字體：大中小

來源：轉載

供稿：網友

快速排序其思想是：先選一個“標尺”，用它把整個隊列過一遍篩子，以保證：其左邊的元素都不大于它，其右邊的元素都不小于它。這樣，排序問題就被分割為兩個子區間。再分別對子區間排序就可以了。

選擇排序思想：重復選擇數組內的最大值，交換到合適的位置。該排序方法比較慢。

堆排序思想：堆實際上是一棵完全二叉樹，利用大頂堆(小頂堆)堆頂記錄的是最大關鍵字(最小關鍵字)這一特性，使得每次從無序中選擇最大記錄(最小記錄)。堆排序其實也是一種選擇排序，是一種樹形選擇排序。

歸并排序思想：這是一個采用分治法的算法，先使每個子序列有序，再使子序列段間有序，再將已有序的子序列合并，這樣就能得到完全有序的序列。桶排序

代碼一起上

#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)