插入：

template<typename DataType>void insert(DataType D[], int length) {DataType key;for (int j = 2; j < length; j++) {key = D[j];//先保存D[j]的位置，因?yàn)樗赡軙?huì)被替換int i = j - 1;while (i > 0 && D[i] > key) {D[i + 1] = D[i];//如果在j前面的元素比該元素大，將該元素后移動(dòng)一個(gè)位置i--;//i繼續(xù)前移進(jìn)行掃描，直到它剛好大于它前面的元素 小于它后面的元素}D[i+1] = key;//插入剛剛的key值 注意是i+1} }//們將D[0]作為哨兵元素，存儲(chǔ)待排序元素

冒泡：

#include<stdio.h> #include<time.h> void swap(int& a, int& b) {int t;t = a;a = b;b = t; } void bubble(int a[], int n) {int i = n - 1;//i是下一趟需要參與排序交換的元素的最大下標(biāo)while (i > 0) {int minindext = 0;//設(shè)置一開(kāi)始的標(biāo)志是0for (int j = 0; j < i; j++) {if (a[j + 1] < a[j]) {swap(a[j + 1], a[j]);}minindext = j;//此時(shí)為交換之后更小的元素的索引}i = minindext;} } int main() {int a[1000] = { 0 };for (int i = 0; i < 1000; i++){a[i] = rand() % 1000 + 1;}bubble(a, 1000);for (int i = 0; i < 1000; i++){cout<<a[i]<<",";}printf("Time used = %.2f\n", (double)clock() / CLOCKS_PER_SEC); }

注意：如果不寫(xiě)swap函數(shù)，而是直接在bubble函數(shù)中交換兩個(gè)數(shù)字，發(fā)現(xiàn)它們最后并沒(méi)有發(fā)生交換。

快速排序:

template<class T> int partition(T data[], int p, int r) {int i = p - 1; int j = p;for (j = p; j < r; j++) {if (data[j] <= data[r]) {i++;swap(data[i], data[j]);}}swap(data[i+1], data[r]);return i + 1; } template <class T> void quickSort(T data[], int p, int r) {int position = 0;if (p < r) {position = partition(data, p, r);quickSort(data, p, position - 1);quickSort(data, position+1, r);} }int main() {int a[1000] = { 0 };for (int i = 0; i < 1000; i++){a[i] = rand() % 1000 + 1;}quickSort(a, 0,999);for (int i = 0; i < 1000; i++){cout<<a[i]<<",";}printf("Time used = %.2f\n", (double)clock() / CLOCKS_PER_SEC); }

易錯(cuò)點(diǎn):swap(data[i+1], data[r]);
return i + 1;注意是i+1 ,如果寫(xiě)成i無(wú)法排序
我們?cè)O(shè)置變量p 和r 表示數(shù)組的首尾元素下標(biāo)，選取數(shù)組最右邊的元素為我們第一次排序的劃界元素，記為S[r]。那么我們就需要將S[p]，S[p+1]，…，S[r–1]組成的序列進(jìn)行子序列劃分
我們?cè)O(shè)置變量i=p–1，即最前面元素的前一個(gè)，設(shè)置變量j = p。反復(fù)執(zhí)行如下步驟：
（1）執(zhí)行j+1，如果S[j]≤S[r]，交換S[i+1]與S[j]的值，i=i+1，j=j+1；如果S[j]≥S[r]，i 不變，j=j+1；
（2）到j(luò)=r–1 時(shí)，停止步驟（1）。
重復(fù)執(zhí)行上述步驟直至停止后，交換S[i+1]與S[r]的值，劃界元素放在了其最終位置上，其左邊的元素均小于等于它，右邊的元素均大于它。

歸并排序：

void merge(int aa[], int b [], int c[],int lenA, int lenB) {int count = 0;int i = 0, j = 0;while (count < lenA + lenB) {if (aa[i] < b[j]) {c[count] = aa[i];count++;i++;}else {c[count] = b[j];count++;j++;}if (i == lenA) {while (j < lenB) {c[count] = b[j];count++;j++;}}else if(j == lenB){while (i < lenA) {c[count] = aa[i];count++;i++;}}} }void mergesort(int a[], int n) {if (n > 1) //記得要加判斷條件n>1{int* b = new int[n / 2];int* c = new int[n - n / 2];for (int i = 0; i < n / 2; i++) {b[i] = a[i];}int k = n / 2;for (int j = 0; j < n - n / 2; j++) {c[j] = a[j + k];}mergesort(b, n / 2);mergesort(c, n - n / 2);merge(b, c, a, n / 2, n - n / 2);} } int main() {int a[1000] = { 0 };for (int i = 0; i < 1000; i++){a[i] = rand() % 1000 + 1;}mergesort(a, 1000);for (int i = 0; i < 1000; i++){cout << a[i] << ",";}printf("Time used = %.2f\n", (double)clock() / CLOCKS_PER_SEC); }

歸并排序是排序兩個(gè)已經(jīng)排序好了的數(shù)組，原數(shù)組要先拆成兩個(gè)子數(shù)組，
注意：一定不能遺漏對(duì)于i和j達(dá)到a或者b末尾的判斷，否則會(huì)出現(xiàn)亂碼。當(dāng)i到達(dá)a的末尾，則遍歷b剩下的數(shù)組直接賦給c

跟之前的對(duì)比歸并排序時(shí)間是最長(zhǎng)的。

總結(jié)

以上是生活随笔為你收集整理的【练习】不同排序算法执行时间比较的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。