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