冒泡排序
起泡排序，別名“冒泡排序”，該算法的核心思想是將無序表中的所有記錄，通過兩兩比較關鍵字，得出升序序列或者降序序列。
算法步驟
- 比較相鄰的元素。如果第一個元素大于第二個元素，就交換它們。
- 對每一對相鄰的元素作相同的操作，從開始第一對到末尾的最后一對。
- 針對所有的元素重復以上操作，每次出來最后一個
算法理解
例如，對無序表{49，38，65，97，76，13，27，49}進行升序排序的具體實現過程如圖 1 所示：
圖 1 第一次起泡
如圖 1 所示是對無序表的第一次起泡排序，最終將無序表中的最大值 97 找到并存儲在表的最后一個位置。具體實現過程為：
- 首先 49 和 38 比較，由于 38<49，所以兩者交換位置，即從（1）到（2）的轉變；
- 然后繼續下標為 1 的同下標為 2 的進行比較，由于 49<65，所以不移動位置，（3）中 65 同 97 比較得知，兩者也不需要移動位置；
- 直至（4），97 同 76 進行比較，76<97，兩者交換位置，如（5）所示；
- 同樣 97>13（5）、97>27（6）、97>49（7），所以經過一次冒泡排序，最終在無序表中找到一個最大值 97，第一次冒泡結束；
由于 97 已經判斷為最大值，所以第二次冒泡排序時就需要找出除 97 之外的無序表中的最大值，比較過程和第一次完全相同。
經過第二次冒泡，最終找到了除 97 之外的又一個最大值 76，比較過程完全一樣，這里不再描述。
通過一趟趟的比較，一個個的“最大值”被找到并移動到相應位置，直到檢測到表中數據已經有序，或者比較次數等同于表中含有記錄的個數，排序結束，這就是起泡排序。
代碼實現
#include "iostream"
using namespace std;void swap(int *a, int *b){//交換a和b的位置int temp;temp = *a;*a = *b;*b = temp;
}
int main()
{int array[8] = {49,38,65,97,76,13,27,49};//有多少記錄，就需要多少次冒泡，當比較過程，所有記錄都按照升序排列時，排序結束for (int i = 0; i < 8; i++){int key=0;//每次開始冒泡前，初始化 key 值為 0//每次起泡從下標為 0 開始，到 8-i 結束for (int j = 0; j+1<8-i; j++){if (array[j] > array[j+1]){key=1;swap(&array[j], &array[j+1]);}}//如果 key 值為 0，表明表中記錄排序完成if (key==0) {break;}}for (i = 0; i < 8; i++){cout << array[i] << " ";}return 0;
}
運行結果：
13 27 38 49 49 65 76 97
總結
使用起泡排序算法，其時間復雜度同實際表中數據的無序程度有關。若表中記錄本身為正序存放，則整個排序過程只需進行 n-1（n 為表中記錄的個數）次比較，且不需要移動記錄；若表中記錄為逆序存放（最壞的情況），則需要 n-1趟排序，進行 n(n-1)/2 次比較和數據的移動。所以該算法的時間復雜度為O(n2)。
快速排序
快速排序本質上是可以說是冒泡排序基礎上的遞歸分治法，它也是分治算法在排序算法上的一種經典應用。
算法思想
快速排序是通過多次比較和交換來實現有序的。在一次排序中把將要排序的元素分成兩個獨立的子數組，其中一個子數組的所有元素全大于另一個組數組的所有元素，然后繼續遞歸排序這兩部分。
算法思想步驟：
- 從序列中挑出一個元素，稱之為邊界或者基準
- 重新排序數列，所有元素比基準值小的放在基準前面，所有元素比基準值大的放在基準后面（相同的數可以放在任意一邊）。這個操作結束后，該基準就處于序列的中間位置，這個操作稱之為分區操作
- 遞歸吧小于基準元素的組數組和大于基準元素的子數組排序
算法理解
代碼實現
#include "iostream"
using namespace std;#define MAX 9
//單個記錄的結構體
typedef struct {int key;
}SqNote;
//記錄表的結構體
typedef struct {SqNote r[MAX];int length;
}SqList;
//此方法中，存儲記錄的數組中，下標為 0 的位置時空著的，不放任何記錄，記錄從下標為 1 處開始依次存放
int Partition(SqList *L,int low,int high){L->r[0]=L->r[low];int pivotkey=L->r[low].key;//直到兩指針相遇，程序結束while (low<high) {//high指針左移，直至遇到比pivotkey值小的記錄，指針停止移動while (low<high && L->r[high].key>=pivotkey) {high--;}//直接將high指向的小于支點的記錄移動到low指針的位置。L->r[low]=L->r[high];//low 指針右移，直至遇到比pivotkey值大的記錄，指針停止移動while (low<high && L->r[low].key<=pivotkey) {low++;}//直接將low指向的大于支點的記錄移動到high指針的位置L->r[high]=L->r[low];}//將支點添加到準確的位置L->r[low]=L->r[0];return low;
}
void QSort(SqList *L,int low,int high){if (low<high) {//找到支點的位置int pivotloc=Partition(L, low, high);//對支點左側的子表進行排序QSort(L, low, pivotloc-1);//對支點右側的子表進行排序QSort(L, pivotloc+1, high);}
}
void QuickSort(SqList *L){QSort(L, 1,L->length);
}
int main() {SqList *L = new SqList;L->length=8;L->r[1].key=49;L->r[2].key=38;L->r[3].key=65;L->r[4].key=97;L->r[5].key=76;L->r[6].key=13;L->r[7].key=27;L->r[8].key=49;QuickSort(L);for (int i=1; i<=L->length; i++) {cout << L->r[i].key << " ";}return 0;
}
運行結果：
13 27 38 49 49 65 76 97
總結
快速排序算法的時間復雜度為O(nlogn)，是所有時間復雜度相同的排序方法中性能最好的排序算法。
