快速排序

主要思想: 主要是基于分治。(分治解讀)

基本步驟:

1.確定分界點(diǎn)x ，常用方式q[l]? q[l + r >> 1] , q[r] , 左右部分未必長度相等

2.根據(jù)分界點(diǎn)x調(diào)整區(qū)間，使得滿足小于等于x的在左邊，大于等于x的在右邊

3.左右兩端，遞歸縮小規(guī)模處理，然后進(jìn)行拼接，即兩個(gè)區(qū)間合并

注釋：其中使用了雙指針算法思想中的，從兩側(cè)向中間移動(dòng)來維護(hù)一段區(qū)間的方法

// 快速排序算法模板 void quick_sort(int q[], int l, int r) {if (l >= r) return;int i = l - 1, j = r + 1, x = q[l + r >> 1];while (i < j){do i ++ ; while (q[i] < x);do j -- ; while (q[j] > x);if (i < j) swap(q[i], q[j]);}quick_sort(q, l, j);quick_sort(q, j + 1, r); }

歸并排序

主要思想: 主要是基于分治。(分治解讀)

基本步驟:

1.確定分界點(diǎn)mid，常用方式l + r >> 1?

2.遞歸排序左邊和右邊

3.歸并合二為一,雙指針?biāo)惴ā蓚€(gè)有序的序列進(jìn)行二合一排序存到額外空間

注釋：其中使用了雙指針算法思想中的，從兩側(cè)向中間移動(dòng)來維護(hù)一段區(qū)間的方法

// 歸并排序算法模板 void merge_sort(int q[], int l, int r) {if (l >= r) return;int mid = l + r >> 1;merge_sort(q, l, mid);merge_sort(q, mid + 1, r);int k = 0, i = l, j = mid + 1;while (i <= mid && j <= r)if (q[i] < q[j]) tmp[k ++ ] = q[i ++ ];else tmp[k ++ ] = q[j ++ ];while (i <= mid) tmp[k ++ ] = q[i ++ ];while (j <= r) tmp[k ++ ] = q[j ++ ];for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j]; }

?歸并排序 自帶時(shí)間復(fù)雜度測試

//時(shí)間復(fù)雜度 O(N*log2N) //穩(wěn)定程度： 穩(wěn)定 /* 確定分界點(diǎn)，中間位置 兩端排序 歸并，合二為一 */#include<iostream> #include<time.h> using namespace std; int tmp[250001]; void Sort(int List[], int l, int r);int main() {int a[250000];int k, j;// 設(shè)置種子srand((unsigned)time(NULL));/* 生成 10 個(gè)隨機(jī)數(shù) */for (k = 0; k < 250000; k++){// 生成實(shí)際的隨機(jī)數(shù)j = rand();a[k] = j;}clock_t start_time = clock();Sort(a,0,250000-1);clock_t end_time = clock();//for (int i = 0; i < 200000; i++)//{// cout << a[i] << " ";//}cout << "\n程序段運(yùn)行時(shí)間：" << static_cast<double> (end_time - start_time) / CLOCKS_PER_SEC * 1000 << "ms" << endl;system("pause"); } void Sort(int List[], int l, int r) {if (l >= r) return;int mid = l + r >> 1; //取中間數(shù)Sort(List, l, mid), Sort(List, mid + 1, r); //左右遞歸排序int k = 0, i = l, j = mid + 1; //k表示已合并數(shù)組中有幾個(gè)元素，分開兩個(gè)有序數(shù)組while (i <= mid && j <= r) //進(jìn)行雙指針比較if (List[i] <= List[j]) tmp[k++] = List[i++]; else tmp[k++] = List[j++];while (i <= mid) tmp[k++] = List[i++]; //分別處理剩余部分while (j <= r) tmp[k++] = List[j++];for (i = l, j = 0; i <= r; i++, j++) List[i] = tmp[j]; //拷入原空間}

快速排序 自帶時(shí)間復(fù)雜度檢測

//時(shí)間復(fù)雜度 O(N*log2N //穩(wěn)定性：不穩(wěn)定 //來源于分治思想 /* 確定分界點(diǎn) 調(diào)整區(qū)間 遞歸處理兩端 算法思想，快排是基于冒泡排序的優(yōu)化，冒泡排序從一側(cè)開始進(jìn)行，而快排是兩邊同時(shí)進(jìn)行從而時(shí)間復(fù)雜度折半，同時(shí)包含了二分的思想在里面 */#include<iostream> #include<time.h> using namespace std;void Sort(int List[], int l, int r);int main() {int a[80000];int k, j;// 設(shè)置種子srand((unsigned)time(NULL));/* 生成 10 個(gè)隨機(jī)數(shù) */for (k = 0; k < 80000; k++){// 生成實(shí)際的隨機(jī)數(shù)j = rand();a[k] = j;}clock_t start_time = clock();Sort(a,0,80000-1);clock_t end_time = clock();for (int i = 0; i < 80000; i++){cout << a[i] << " ";}cout << "\n程序段運(yùn)行時(shí)間：" << static_cast<double> (end_time - start_time) / CLOCKS_PER_SEC * 1000 << "ms" << endl;system("pause"); } void Sort(int List[], int l, int r) {if (l >= r) return; //邊界判斷int i = l - 1, j = r + 1, x = List[l]; //x為分界點(diǎn)while (i < j){//兩次do，主要在于找到左右兩側(cè)<x和>x的第一個(gè)數(shù)do i++; while (List[i] < x); do j--; while (List[j] > x);if (i < j) swap(List[i], List[j]);else break;}Sort(List, l, j), Sort(List, j + 1, r);}

冒泡排序 自帶時(shí)間復(fù)雜度測試

#include<iostream> #include<time.h> using namespace std;void Sort(int List[], int n);int main() {int a[10000];int k, j;// 設(shè)置種子srand((unsigned)time(NULL));/* 生成 10 個(gè)隨機(jī)數(shù) */for (k = 0; k < 10000; k++){// 生成實(shí)際的隨機(jī)數(shù)j = rand();a[k] = j;}clock_t start_time = clock();Sort(a, 10000);clock_t end_time = clock();for (int i = 0; i < 10000; i++){cout << a[i] << " ";}cout << "\n程序段運(yùn)行時(shí)間：" << static_cast<double> (end_time - start_time) / CLOCKS_PER_SEC * 1000 << "ms" << endl;system("pause"); } void Sort(int List[], int n) {for (int i = 0; i < n - 1; i++){for (int j = 0; j < n - i - 1; j++) //j<n-i-1:首先j不與自己比較所以-1，其次每次外循環(huán)都會(huì)產(chǎn)生一個(gè)已經(jīng)排序的最大數(shù)，所以內(nèi)循環(huán)要排除已經(jīng)排好的，即總數(shù)為n-i。if (List[j] > List[j + 1])swap(List[j], List[j + 1]);} }

冒泡排序優(yōu)化

#include<iostream> #include<time.h> using namespace std;void Sort(int List[], int n);int main() {int a[10000];int k, j;// 設(shè)置種子srand((unsigned)time(NULL));/* 生成 10 個(gè)隨機(jī)數(shù) */for (k = 0; k < 10000; k++){// 生成實(shí)際的隨機(jī)數(shù)j = rand();a[k] = j;}clock_t start_time = clock();Sort(a, 10000);clock_t end_time = clock();for (int i = 0; i < 10000; i++){cout << a[i] << " ";}cout << "\n程序段運(yùn)行時(shí)間：" << static_cast<double> (end_time - start_time) / CLOCKS_PER_SEC * 1000 << "ms" << endl;system("pause"); } void Sort(int List[], int n) {bool sorted = false; //整體排序標(biāo)志標(biāo)志，首先假定尚未排序while (!sorted){sorted = true; //假定已經(jīng)排序for (int j = 1; j < n -1; j++) //j<n-i-1:首先j不與自己比較所以-1，其次每次外循環(huán)都會(huì)產(chǎn)生一個(gè)已經(jīng)排序的最大數(shù)，所以內(nèi)循環(huán)要排除已經(jīng)排好的，即總數(shù)為n-i。if (List[j - 1] > List[j]){swap(List[j - 1], List[j]);sorted = false;//因整體排序不能保證，需要清除排序標(biāo)志}}n--;//至此元素必然就位，故可以縮短待排序序列的有效長度}//借助布爾型標(biāo)志位sorted，可及時(shí)提前退出，而丌致總是蠻力地做n - 1趟掃描交換

選擇排序 自帶時(shí)間復(fù)雜度分析

從當(dāng)前未排序的整數(shù)中找到最小的整數(shù)，將它放在已排序的整數(shù)列表的最后。 #include<iostream> #include<time.h> using namespace std;void Sort(int List[], int n);int main() {int a[10000];int k, j;// 設(shè)置種子srand((unsigned)time(NULL));/* 生成 10 個(gè)隨機(jī)數(shù) */for (k = 0; k < 10000; k++){// 生成實(shí)際的隨機(jī)數(shù)j = rand();a[k] = j;}clock_t start_time = clock();Sort(a, 10000);clock_t end_time = clock();for (int i = 0; i < 10000; i++){cout << a[i] << " ";}cout << "\n程序段運(yùn)行時(shí)間：" << static_cast<double> (end_time - start_time) / CLOCKS_PER_SEC * 1000 << "ms" << endl;system("pause"); } void Sort(int List[], int n) {for (int i = 0; i < n - 1; i++){int min = i;//min處,假設(shè)第一個(gè)是最小的,是;數(shù)組的下標(biāo)for (int j = i + 1; j < n; j++) //j=i+1是因?yàn)橹耙呀?jīng)掃描過了{(lán)if (List[j] < List[min]){min = j; //移動(dòng)記錄下來}}swap(List[i], List[min]); //掃描一遍結(jié)束后，交換一次} }

選擇排序與冒泡排序的區(qū)別

冒泡排序：
?
冒泡排序（BubbleSort）的基本概念是：依次比較相鄰的兩個(gè)數(shù)，將小數(shù)放在前面，大數(shù)放在后面。即在第一趟：首先比較第1個(gè)和第2個(gè)數(shù)，將小數(shù)放前，大數(shù) 放后。
?
然后比較第2個(gè)數(shù)和第3個(gè)數(shù)，將小數(shù)放前，大數(shù)放后，如此繼續(xù)，直至比較最后兩個(gè)數(shù)，將小數(shù)放前，大數(shù)放后。至此第一趟結(jié)束，將最大的數(shù)放到了最后。
?
在第二趟：仍從第一對(duì)數(shù)開始比較（因?yàn)榭赡苡捎诘?個(gè)數(shù)和第3個(gè)數(shù)的交換，使得第1個(gè)數(shù)不再小于第2個(gè)數(shù)），將小數(shù)放前中，大數(shù)放后，一直比較到倒數(shù)第二個(gè)數(shù)（倒數(shù)第一的位置上已經(jīng)是最大的），第二趟結(jié)束，在倒數(shù)第二的位置上得到一個(gè)新的最大數(shù)（其實(shí)在整個(gè)數(shù)列中是第二大的數(shù)）。如此下去，重復(fù)以上過程，直至最終完成排序。
?
選擇排序
?
第一次從下標(biāo)為0的開始下標(biāo)為0的這個(gè)數(shù)與后面的n-1個(gè)進(jìn)行比較；找出最小或者最大的放在下標(biāo)為0的這個(gè)位置；第二次從下標(biāo)為1的開始比較；查詢剩下的最大或者最小值；放在下標(biāo)為1的位置；以此類推；直到排序完成。
?
總結(jié)
?
從上兩段代碼可以看出,它們處于同一個(gè)數(shù)量級(jí)，即時(shí)間復(fù)雜度是相同的,都用了兩層循環(huán),為O(n^2)(n:排序個(gè)數(shù)); 但是內(nèi)層循環(huán)中，冒泡排序的互換位置的操作從概率上講要明顯多于選擇排序. 整個(gè)排序算法，選擇排序換位操作為O(n)，冒泡排序?yàn)镺(n^2/2). 所以綜合來講選擇排序的時(shí)間效率要高于冒泡排序.

總結(jié)

以上是生活随笔為你收集整理的各种排序算法思想的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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