看了總結(jié)圖，我這里就總結(jié)一下 直接插入排序，冒泡排序，快速排序，堆排序和歸并排序，使用C++實(shí)現(xiàn)
重新畫了總結(jié)圖
直接插入排序
整個(gè)序列分為有序區(qū)和無序區(qū)，取第一個(gè)元素作為初始有序區(qū)，然后第二個(gè)開始，依次插入到有序區(qū)的合適位置，直到排好序
剛開始在我那本《數(shù)據(jù)結(jié)構(gòu)》看到大概這樣的實(shí)現(xiàn)
void InsertSort(int arr[], int len) {
int i, j;
int temp;
for (i = 1; i < len; i++) {
temp = arr[i];
for (j = i - 1; j >= 0 && arr[j] > temp;j--)
arr[j + 1] = arr[j];
arr[j + 1] = temp;
}
}
有點(diǎn)難理解，后來又在網(wǎng)上看到這樣的實(shí)現(xiàn)，這種方式比較好理解
void InsertSort(int arr[],int n){
for (int i =1;i <= n;++i){
for(int j = i;j > 0;--j){
if(arr[j] < arr[j -1]){
int temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
}
}
}
}
原理都是一樣的，第一個(gè)for循環(huán)對(duì)從第二個(gè)開始的所有的數(shù)字遍歷，嵌套的for循環(huán)是每次遍歷數(shù)字時(shí)都取無序區(qū)的一個(gè)元素與有序區(qū)的元素比較，如果比有序區(qū)的要小則交換，直到合適的位置。
如果使用vector的話會(huì)方便一點(diǎn)，因?yàn)関ector可以使用size()直接獲得容器內(nèi)的元素個(gè)數(shù)
void InsertSort2(vector<int> &num){
for(int i = 1;i < num.size();++i){
for(int j = i;j > 0;--j){
if(num[j] < num[j - 1]){
int temp = num[j];
num[j] = num[j-1];
num[j-1] = temp;
}
}
}
}
插入排序的時(shí)間復(fù)雜度最好的情況是已經(jīng)是正序的序列，只需比較(n-1)次，時(shí)間復(fù)雜度為O(n)，最壞的情況是倒序的序列，要比較n(n-1)/2次，時(shí)間復(fù)雜度為O(n^2 ) ，平均的話要比較時(shí)間復(fù)雜度為O(n^2 )
插入排序是一種穩(wěn)定的排序方法，排序元素比較少的時(shí)候很好，大量元素便會(huì)效率低下
這個(gè)圖很形象，取自維基百科
冒泡排序
比較相鄰的元素，如果反序則交換，過程也是分為有序區(qū)和無序區(qū)，初始時(shí)有序區(qū)為空，所有元素都在無序區(qū)，經(jīng)過第一趟后就能找出最大的元素，然后重復(fù)便可
void BubbleSort(int arr[], int n)
{
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
冒泡排序感覺非常好理解，第一個(gè)for循環(huán)是遍歷所有元素，第二個(gè)for循環(huán)是每次遍歷元素時(shí)都對(duì)無序區(qū)的相鄰兩個(gè)元素進(jìn)行一次比較，若反序則交換
時(shí)間復(fù)雜度最壞的情況是反序序列，要比較n(n-1)/2次，時(shí)間復(fù)雜度為O(n^2 )，最好的情況是正序，只進(jìn)行(n-1)次比較，不需要移動(dòng)，時(shí)間復(fù)雜度為O(n)，而平均的時(shí)間復(fù)雜度為O(n^2 )
但是還有更好的方法，如果第一次比較完沒有交換即說明已經(jīng)有序，不應(yīng)該進(jìn)行下一次遍歷
還有已經(jīng)遍歷出部分有序的序列后，那部分也不用進(jìn)行遍歷，即發(fā)生交換的地方之后的地方不用遍歷
void BubbleSort(int arr[], int len){
int i,temp;
//記錄位置，當(dāng)前所在位置和最后發(fā)生交換的地方
int current,last = len - 1;
while(last > 0) {
for(i = current = 0;i < last;++i){
if(arr[i] > arr[i+1]){
temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
//記錄當(dāng)前的位置，如果沒有發(fā)生交換current值即for循環(huán)初始化的0
current = I;
}
}
//若current = 0即已經(jīng)沒有可以交換的元素了，即已經(jīng)有序了
last = current;
}
}
冒泡排序也是一種穩(wěn)定的排序算法，也是元素較少時(shí)效率比較高
快速排序
快速排序首先選一個(gè)軸值(pivot，也有叫基準(zhǔn)的)，將待排序記錄劃分成獨(dú)立的兩部分，左側(cè)的元素均小于軸值，右側(cè)的元素均大于或等于軸值，然后對(duì)這兩部分再重復(fù)，直到整個(gè)序列有序
過程是和二叉搜索樹相似，就是一個(gè)遞歸的過程
排序函數(shù)
QuickSort(int arr[], int first, int end){
if (first < end) {
int pivot = OnceSort(arr,first,end);
//已經(jīng)有軸值了，再對(duì)軸值左右進(jìn)行遞歸
QuickSort(arr,first,pivot-1);
QuickSort(arr,pivot+1,end);
}
}
接下來就是一次排序的函數(shù)
int OnceSort(int arr[], int first, int end){
int i = first,j = end;
//當(dāng)i<j即移動(dòng)的點(diǎn)還沒到中間時(shí)循環(huán)
while(i < j){
//右邊區(qū)開始，保證i<j并且arr[i]小于或者等于arr[j]的時(shí)候就向左遍歷
while(i < j && arr[i] <= arr[j]) --j;
//這時(shí)候已經(jīng)跳出循環(huán)，說明j>i 或者 arr[i]大于arr[j]了，如果i<j那就是arr[i]大于arr[j]，那就交換
if(i < j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
//對(duì)另一邊執(zhí)行同樣的操作
while(i < j && arr[i] <= arr[j]) ++I;
if(i < j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
//返回已經(jīng)移動(dòng)的一邊當(dāng)做下次排序的軸值
return I;
}
過程解釋都寫在注釋里面了，挺好理解的
這是我在書上看到的實(shí)現(xiàn)，用的是遞歸的方法
我在維基上還看到用迭代的方法，這里就不說了，有興趣的可以去看看
這個(gè)圖不是一般的棒??！來自維基
快速排序時(shí)間復(fù)雜度的最好情況和平均情況一樣為O(nlog2 n)，最壞情況下為O(n^2 )，這個(gè)看起來比前面兩種排序都要好，但是這是不穩(wěn)定的算法，并且空間復(fù)雜度高一點(diǎn)（ O(nlog2 n)
而且快速排序適用于元素多的情況
堆排序
堆的結(jié)構(gòu)類似于完全二叉樹，每個(gè)結(jié)點(diǎn)的值都小于或者等于其左右孩子結(jié)點(diǎn)的值，或者每個(gè)節(jié)點(diǎn)的值都大于或等于其左右孩子的值
堆排序過程將待排序的序列構(gòu)造成一個(gè)堆，選出堆中最大的移走，再把剩余的元素調(diào)整成堆，找出最大的再移走，重復(fù)直至有序
來看一下實(shí)現(xiàn)
//堆排序
void HeapSort(int arr[],int len){
int I;
//初始化堆，從最后一個(gè)父節(jié)點(diǎn)開始
for(i = len/2 - 1; i >= 0; --i){
Heapify(arr,i,len);
}
//從堆中的取出最大的元素再調(diào)整堆
for(i = len - 1;i > 0;--i){
int temp = arr[i];
arr[i] = arr[0];
arr[0] = temp;
//調(diào)整成堆
Heapify(arr,0,i);
}
}
再看 調(diào)整成堆的函數(shù)
void Heapify(int arr[], int first, int end){
int father = first;
int son = father * 2 + 1;
while(son < end){
if(son + 1 < end && arr[son] < arr[son+1]) ++son;
//如果父節(jié)點(diǎn)大于子節(jié)點(diǎn)則表示調(diào)整完畢
if(arr[father] > arr[son]) break;
else {
//不然就交換父節(jié)點(diǎn)和子節(jié)點(diǎn)的元素
int temp = arr[father];
arr[father] = arr[son];
arr[son] = temp;
//父和子節(jié)點(diǎn)變成下一個(gè)要比較的位置
father = son;
son = 2 * father + 1;
}
}
}
堆排序的時(shí)間復(fù)雜度最好到最壞都是O(nlogn)，較多元素的時(shí)候效率比較高
圖來自維基
我們也可以用遞歸的思想，每次合并就是一次遞歸
首先，將一整個(gè)序列分成兩個(gè)序列，兩個(gè)會(huì)分成4個(gè)，這樣分下去分到最小單位，然后開始合并
void Merge(int arr[], int reg[], int start, int end) {
if (start >= end)return;
int len = end - start, mid = (len >> 1) + start;
//分成兩部分
int start1 = start, end1 = mid;
int start2 = mid + 1, end2 = end;
//然后合并
Merge(arr, reg, start1, end1);
Merge(arr, reg, start2, end2);
int k = start;
//兩個(gè)序列一一比較,哪的序列的元素小就放進(jìn)reg序列里面,然后位置+1再與另一個(gè)序列原來位置的元素比較
//如此反復(fù),可以把兩個(gè)有序的序列合并成一個(gè)有序的序列
while (start1 <= end1 && start2 <= end2)
reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
//然后這里是分情況,如果arr2序列的已經(jīng)全部都放進(jìn)reg序列了然后跳出了循環(huán)
//那就表示arr序列還有更大的元素(一個(gè)或多個(gè))沒有放進(jìn)reg序列,所以這一步就是接著放
while (start1 <= end1)
reg[k++] = arr[start1++];
//這一步和上面一樣
while (start2 <= end2)
reg[k++] = arr[start2++];
//把已經(jīng)有序的reg序列放回arr序列中
for (k = start; k <= end; k++)
arr[k] = reg[k];
}
void MergeSort(int arr[], const int len) {
//創(chuàng)建一個(gè)同樣長度的序列,用于臨時(shí)存放
int reg[len];
Merge(arr, reg, 0, len - 1);
}
過程解釋都寫在了注釋里
歸并排序的時(shí)間復(fù)雜度都是O(nlogn)，并且適用于元素較多的時(shí)候排序
參考資料
1 《數(shù)據(jù)結(jié)構(gòu)(C++版)》
2 維基百科
