排序算法C++程序
文章目錄
- 排序算法程序
- 1、冒泡排序
- 2、直接插入排序
- 3、希爾排序
- 4、快速排序
- 5、總結(jié)
排序算法程序
1、冒泡排序
通過對相鄰數(shù)據(jù)的元素進行交換，逐步將待排序序列排成有序序列的過程。
如升序排列：
- 掃描整個待排序序列（非整個序列，不掃描已經(jīng)排好的序列）
- 在一趟掃描中，最終必然將最大的元素排在待排序序列的末尾，這也是最大元素應(yīng)該在的位置
- 第一趟排序之后，將最大的元素排在最后一個位置，第二趟將次大的放到倒數(shù)第二個位置…
輸出：
#include<iostream> using namespace std; template<typename T> void bubble( T t[],int len)//注意模板中的參數(shù)T為參數(shù)類型，所以不能寫成T[] {bool flag=true;int i,j;for(i=1;i<=len-1&&flag;i++){flag=false;for(j=0;j<len-i;j++)//如果外層循環(huán)是從1開始，那么內(nèi)層循環(huán)j<len-i,//不能取等號，否則會產(chǎn)生下標(biāo)越界，因為下面的交換判斷語句為t[j]//與t[j+1]，{if(t[j]>t[j+1]){swap(t[j],t[j+1]);flag=true;}}} }void main() {int a[]={4,2,1,3,5,7,6};char x[100]={'x','y','s','a','n','c','m'};//此處必須指定數(shù)組的大小，雖然不指定也不會出錯，但是當(dāng)用字符去初始化一個沒定義長度的字符數(shù)組時，系統(tǒng)不會默認在//末尾添加'\0'，所以此時不能用strlen函數(shù)來求該字符數(shù)組的長度，而當(dāng)指定數(shù)組的大小后，余下的系統(tǒng)自動賦值為空，即'\0'// int len=strlen(a);錯誤，strlen函數(shù)的參數(shù)為char*類型int len=sizeof(a)/4;for(int i=0;i<len;i++)cout<<a[i]<<' ';cout<<endl;cout<<"排序后結(jié)果為"<<endl;bubble(a,len);for(int i=0;i<len;i++)cout<<a[i]<<' ';cout<<endl;int str_len=strlen(x);for(int i=0;i<len;i++)cout<<x[i]<<' ';cout<<endl;cout<<"排序后結(jié)果為"<<endl;bubble(x,str_len);for(int i=0;i<len;i++)cout<<x[i]<<' ';cout<<endl;}2、直接插入排序
基本操作是將一個記錄插入到已經(jīng)排好的有序表中，從而得到一個新的、記錄增1的有序表。
也就是將第一個數(shù)作為已經(jīng)排好的序列，第二個數(shù)是插入其左邊還是右邊的情況。
#include <iostream> #include <stdlib.h>#define MAXSIZE 10 //排序用的順序表結(jié)構(gòu) typedef struct {int r[MAXSIZE + 1];//用于存儲要排序數(shù)組，r[0]用做哨兵或臨時變量int length; }SqList;//交換兩個值 void swap(SqList *L, int i, int j){int temp = L->r[i];L->r[i] = L->r[j];L->r[j] = temp; }//直接插入排序void InsertSort(SqList *L) {int i, j,p;for (i = 2; i <= L->length; i++){if (L->r[i] < L->r[i - 1]){L->r[0] = L->r[i]; //設(shè)置哨兵for (j = i - 1; L->r[j]>L->r[0]; j--){L->r[j + 1] = L->r[j];}L->r[j + 1] = L->r[0];}printf("\n\n第%d次排序結(jié)果為：\n\n", i);for (p = 1; p < L->length + 1; p++){printf("%3d", L->r[p]);}}}int main() {int x, y;SqList L;L.length = 10;printf("待排序的序列為為：\n");for (x = 1; x < 11; x++){y = rand() % 10;L.r[x] = y;printf("%3d", y);}InsertSort(&L);getchar();return 0; }輸出：
3、希爾排序
基于增量“inception”對序列進行分割
第一次：inception=length/3+1，i=inception+1，將第i位和第i-inception位比較
第二次：inception=inception/3+1，i=inception+1
直到inception=1為止
4、快速排序
快速排序作為和冒泡排序相同類型的排序（同為交換類排序），之所以能夠被人們所熟知，是因為它解決了冒泡排序只用來對相鄰兩個元素進行比較，因此在互換兩個相鄰元素時只能消除一個逆序，而快速排序是通過兩個不相鄰元素的交換，來消除待排序記錄中的多個逆序。即快速排序中的一趟交換可以消除多個逆序。
具體思想：
從待排序記錄中選取一個記錄（通常選取第一個記錄，當(dāng)然也可采用隨機劃分的方式，這樣能大大提高快速排序的執(zhí)行效率，如我們所熟知的在O(n)的時間復(fù)雜度內(nèi)找出前k元的算法），將其關(guān)鍵字記為K1，然后將其余關(guān)鍵字小于K1的記錄移到前面，而大于關(guān)鍵字K1的移到后面。
一趟快速排序之后，將待排序序列劃分為兩個子表，最后將關(guān)鍵字K1插到這兩個子表的分界線的位置。具體實現(xiàn)就是用三層while循環(huán)，最外層的while循環(huán)控制該趟快速是否進行，而內(nèi)層的兩個while循環(huán)一個用來從左到右掃描大于該趟基準(zhǔn)記錄關(guān)鍵字的元素，一個用來從右到左掃描小于該趟基準(zhǔn)記錄的關(guān)鍵字的元素，可以用兩個指針low和high指向當(dāng)前從左到右和從右到左掃描的當(dāng)前記錄的關(guān)鍵字，找到一個就將其交換。
以上是一趟快速排序的思想，對上述劃分后的子表重復(fù)上述過程，直至劃分后的子表的長度不超過1為止。即為快速排序的思想，從定義可知快速排序是一個遞歸排序。
#include <iostream> #include <stdlib.h>#define MAXSIZE 10 //排序用的順序表結(jié)構(gòu) typedef struct {int r[MAXSIZE + 1];//用于存儲要排序數(shù)組，r[0]用做哨兵或臨時變量int length; }SqList;//交換兩個值 void swap(SqList *L, int i, int j) {int temp = L->r[i];L->r[i] = L->r[j];L->r[j] = temp; }void QuickSort(SqList *L); void QSort(SqList *L, int low, int high); int Partition(SqList *L, int low, int high);int main() {int x, y;SqList L;L.length = 10;printf("待排序的序列為：\n");for (x = 1; x < 11; x++){y = rand() % 10;L.r[x] = y;printf("%3d", y);}QuickSort(&L);getchar();return 0; }//快速排序void QuickSort(SqList *L) {QSort(L, 1, L->length);}void QSort(SqList *L, int low, int high) {int pivot,p;if (low < high){pivot = Partition(L, low, high);QSort(L, low, pivot - 1);QSort(L, pivot + 1, high);}}int Partition(SqList *L, int low, int high) {int pivotkey;pivotkey = L->r[low];while (low < high){while (low < high && L->r[high] >= pivotkey){high--;}swap(L, low, high);while (low < high && L->r[low] <= pivotkey){low++;}swap(L, low, high);}return low;}5、總結(jié)
穩(wěn)定性：排序算法的穩(wěn)定性:若待排序的序列中，存在多個具有相同關(guān)鍵字的記錄，經(jīng)過排序， 這些記錄的相對次序和排序之前相同，則稱該算法是穩(wěn)定的；
若排序后，記錄的相對次序和排序前不同，則該算法是不穩(wěn)定的。
穩(wěn)定的排序算法：冒泡排序、插入排序、歸并排序和基數(shù)排序
不是穩(wěn)定的排序算法：選擇排序、快速排序、希爾排序、堆排序
當(dāng)待排序序列順序或基本有序時，直接插入排序和冒泡排序?qū)⒋蟠鬁p少比較次數(shù)和移動記錄的次數(shù)，時間復(fù)雜度可降至O（n）；
而快速排序則相反，當(dāng)待排序序列基本有序時，將蛻化為冒泡排序，時間復(fù)雜度提高為O（n2）；
待排序序列是否有序，對簡單選擇排序、堆排序、歸并排序和基數(shù)排序的時間復(fù)雜度影響不大。
下面是轉(zhuǎn)于別人的程序
#include <stdio.h> #include <stdlib.h> #define MAXSIZE 100//排序用的順序表結(jié)構(gòu) typedef struct{int r[MAXSIZE + 1];//用于存儲要排序數(shù)組，r[0]用做哨兵或臨時變量int length; }SqList;//交換兩個值 void swap(SqList *L, int i, int j){int temp = L->r[i];L->r[i] = L->r[j];L->r[j] = temp; }//冒泡排序 void BubbleSort(SqList *L){int i, j, k = 0, l = 0;for (i = 1; i<L->length; i++){//外層循環(huán)，確定所有數(shù)都與其它數(shù)比較//k++;for (j = i + 1; j <= L->length; j++){//內(nèi)層循環(huán)，用一個數(shù)跟其它數(shù)比較大小k++;if (L->r[i] > L->r[j]){swap(L, i, j);l = l + 3;}}}printf("冒泡排序中關(guān)鍵字的比較次數(shù)為%d:", k);printf("\n冒泡排序中關(guān)鍵字的移動次數(shù)為%d:", l);printf("\n"); }//直接排序 void InsertSort(SqList *L) {int i, j, k = 0, l = 0;for (i = 2; i <= L->length; i++){k++;if (L->r[i] < L->r[i - 1]){L->r[0] = L->r[i];//設(shè)置哨兵l++;for (j = i - 1; L->r[j] > L->r[0]; j--){L->r[j + 1] = L->r[j];//記錄后移l++;k++;}k++;//這一步容易忽略，跳出循環(huán)的時候，是比較了一次，不符合條件才跳出的L->r[j + 1] = L->r[0];//插入到正確位置l++;}}printf("直接排序中關(guān)鍵字的比較次數(shù)為%d:", k);printf("\n直接排序中關(guān)鍵字的移動次數(shù)為%d:", l);printf("\n"); }//簡單選擇排序 void SelectSort(SqList *L){int i, j, min;int k = 0, l = 0;for (i = 1; i<L->length; i++){//k++;min = i;for (j = i + 1; j <= L->length; j++){k++;if (L->r[min] > L->r[j]){min = j;}}if (i != min){//判斷 i!min，則證明有數(shù)據(jù)比 r[min]還要小，則需交換swap(L, i, min);l = l + 3;}}printf("簡單排序中關(guān)鍵字的比較次數(shù)為:%d", k);printf("\n簡單排序中關(guān)鍵字的移動次數(shù)為:%d", l);printf("\n"); }//希爾排序 void ShellSort(SqList *L) {int i, j;int k = 0, l = 0;int increment = L->length;do{increment = increment / 5 + 1;//增量序列for (i = increment + 1; i <= L->length; i++){k++;if (L->r[i] < L->r[i - increment]){// 需要將L->r[i]插入有序增量子表L->r[0] = L->r[i];l++;for (j = i - increment; L->r[0]<L->r[j] && j>0; j = j - increment){k++;L->r[j + increment] = L->r[j];l++;}k++;//這一步容易忽略，跳出循環(huán)的時候，是比較了一次，不符合條件才跳出的L->r[j + increment] = L->r[0];l++;}}} while (increment > 1);printf("希爾排序中關(guān)鍵字的比較次數(shù)為:%d", k);printf("\n希爾排序中關(guān)鍵字的移動次數(shù)為:%d", l);printf("\n"); }//已知L->r[s..m]中記錄的關(guān)鍵字除L->r[s]之外均滿足堆的定義 //本函數(shù)調(diào)整L->r[s]的關(guān)鍵字，使L->r[s..m]成為一個大頂堆 void HeapAdjust(SqList *L, int s, int m, int &a, int &b){int temp, j;temp = L->r[s];b++;for (j = 2 * s; j <= m; j = j * 2){a++;if (L->r[j] < L->r[j + 1] && j<m)++j;//j為關(guān)鍵字中較大的記錄的下標(biāo)a++;if (temp >= L->r[j])break;L->r[s] = L->r[j];b++;s = j;}L->r[s] = temp;b++; } //堆排序 void HeapSort(SqList *L) {int i;int k = 0, l = 0;for (i = L->length / 2; i>0; i--){//把L中的r構(gòu)建成一個大頂堆HeapAdjust(L, i, L->length, k, l);}for (i = L->length; i>1; i--){swap(L, 1, i);//將堆頂記錄和當(dāng)前未經(jīng)排序子序列的最后一個記錄交換l = l + 3;HeapAdjust(L, 1, i - 1, k, l);//將L->r[1...i-1]重新調(diào)整為大頂堆}printf("堆排序中關(guān)鍵字的比較次數(shù)為:%d", k);printf("\n堆排序中關(guān)鍵字的移動次數(shù)為:%d", l);printf("\n"); }//交換順序表L中子表的記錄，使樞軸記錄到位，并返回其所在位置 //此時在它之前（后）的記錄均不大（小）于它 int Partition(SqList *L, int low, int high, int &k, int &l){int pivotkey;pivotkey = L->r[low];while (low<high){while (L->r[high] >= pivotkey && low<high){k++;high--;}k++;//這一步容易忽略，跳出循環(huán)的時候，是比較了一次，不符合條件才跳出的swap(L, low, high);l = l + 3;while (L->r[low] <= pivotkey && low<high){k++;low++;}k++;//這一步容易忽略，跳出循環(huán)的時候，是比較了一次，不符合條件才跳出的swap(L, low, high);l = l + 3;}return low; } //對順序表L中的子序列L->r[low..high]作快速排序 void QSort(SqList *L, int low, int high, int &k, int &l){int pivot;//樞軸if (low<high){pivot = Partition(L, low, high, k, l);//將L->r[low..high]一分為二，算出樞軸值QSort(L, low, pivot - 1, k, l);//對低子表遞歸排序QSort(L, pivot + 1, high, k, l);//對高子表遞歸排序} }//快速排序 void QuickSort(SqList *L) {int k = 0, l = 0;QSort(L, 1, L->length, k, l);printf("快速排序中關(guān)鍵字的比較次數(shù)為:%d", k);printf("\n快速排序中關(guān)鍵字的移動次數(shù)為:%d", l);printf("\n"); }int main(){int x, y;SqList L, L1, L2, L3, L4, L5;L.length = 100;for (int i = 0; i<5; i++){printf("第%d次待排序列為：\n", i + 1);for (x = 1; x<101; x++) {y = rand() % 100;L.r[x] = y;printf("%3d", y);}L1 = L2 = L3 = L4 = L5 = L;//fflush(stdin);printf("\n排序后的結(jié)果\n");BubbleSort(&L);printf("直接排序后的結(jié)果\n");InsertSort(&L1);printf("簡單排序后的結(jié)果\n");SelectSort(&L2);printf("希爾排序后的結(jié)果\n");ShellSort(&L3);printf("堆排序后的結(jié)果\n");HeapSort(&L4);printf("快速排序后的結(jié)果\n");QuickSort(&L5);for (x = 1; x<101; x++) {printf("%3d", L.r[x]);}printf("\n");}while (1){//設(shè)置一個死循環(huán)，為了不讓程序結(jié)束而關(guān)閉窗口}return 0; }總結(jié)
- 上一篇： 数据结构知识点
- 下一篇： 苹果是否需要换电池测得出来吗(苹果官网报