七大排序

1.排序的基本概念與分類

①排序的基本概念

假設有n個記錄的序列為{r1, r2, …, rn},其對應的關鍵字分別為{k1, k2, k3, …, kn},需要確定1, 2, …, n的一種排列p1, p2, …, pn,使得其對應的關鍵字滿足，kp1 ≤ kp2 ≤ … ≤ kpn，即使得序列稱為一個按關鍵字有序的序列{rp1, rp2, … rpn}，這樣的操作就叫做排序，

如：序列關鍵字為{2, 3, 5, 1},對其進行升序排列后，得到的結果為{1, 2, 3, 5}，

②排序的穩定性

排序不僅可以針對主關鍵字排序（一個主關鍵字對應一條唯一的記錄），也可以針對次關鍵字排序（一條次關鍵字對應多條記錄），因為排序的記錄序列中可能出現兩個或兩個以上的關鍵字相等的記錄，排序結果可能出現不唯一的情況，因此我們給出了穩定與不穩定排序的定義如下：

假設ki = kj(i ≤ i ≤ n， 1 ≤ j ≤ n， i ≠ j),且在排序前的序列中ri領先于rj(i ＜ j)，如果排序后ri仍領先rj，則稱為所用的排序方法是穩定的；反之，可能使得排序后的序列中rj領先于ri，則稱所用的排序方法是不穩定的，

如：下記錄表對分數進行升序排列，

未排序時張三在錢六前面，對于穩定排序后，張三依舊在錢六前面；然而對于不穩定排序，可能出現張三在錢六前面，也可能出現錢六在張三前面，

③內排序與外排序

內排序：在排序整個程序中，待排序的所有記錄全部放置在記憶體中，

外排序：由于排序的記錄太多，不能同時放在記憶體中，整個排序程序需要在內外存之間多次交換資料才能進行，

④影響排序演算法的性能的因素

• 時間性能：排序演算法的時間開銷是衡量其好壞的最重要標志，用時間復雜度O來表示，
• 輔助空間： 輔助存盤空間是除了存放待排序所占用的存盤空間之外，執行演算法所需要的其他存盤空間，
• 演算法的復雜性： 指的是演算法本身的復雜度，而不是時間復雜度，

2.冒泡排序

冒泡排序是一種交換排序，它的基本思想是：兩兩比較相鄰記錄的關鍵字，如果反序則交換，直到沒有反序的記錄為止，

每一次冒泡將序列未排序部分的最大值冒泡到未排序部分序列末尾，

如：待排序序列是{9，5，1，8，3}，序列長度為5，

先來看第一次冒泡程序：

黃色為待排序序列，紅色代表已經排序完成的部分，每一次冒泡是對上一次冒泡后的待排序序列進行排序， 整個排序程序如下圖：

其C++代碼如下：

void bubbleSort(vector<int> &nums) {
    //設記錄序列長度為n
    //外回圈，冒泡次數為n-1次
    for (int i = 0; i < nums.size() - 1; ++i) {
        //內回圈，每一次冒泡需要比較n - i次
        for (int j = 1; j < nums.size() - i; ++j) {
            if (nums[j] < nums[j - 1]) {
            swap(nums[j], nums[j - 1]);
            }
        }
    }
}

冒泡排序時間復雜度為：O(n^2)，

冒泡排序空間復雜度為：O(1)，

3.簡單選擇排序

簡單選擇排序演算法就是通過n - i次關鍵字間的比較，從n - i + 1個記錄中選出關鍵字最小的記錄，并和第i(1 ≤ i ≤ n)個記錄交換，

每次從待排序列種選出一個最小值，然后與待排序序列的第一個元素互換，直到全部待排序列資料排完即可，

如：待排序序列為{9，5，1，8，3}，序列長度為5

先來看一次選擇程序：

黃色為待排序序列，紅色代表已經排序完成的部分，每一次選擇是對上一次選擇后的待排序序列進行排序， 整個排序程序如下圖：

其C++代碼如下：

void selectSort(vector<int> &nums) {
    //設記錄序列長度為n
    //外回圈，選擇次數為n-1次
    for (int i = 0; i < nums.size() - 1; ++i) {
        int min = i; //選擇待排序序列的第一個元素作為每次選擇開始的最小值
        //內回圈，每一次選擇需要比較n - i - 1次
        for (int j = i + 1; j < nums.size(); ++j) {
            if (nums[j] < nums[min]) {
                min = j;
            }
        } 
        if (min != i) {
            swap(nums[i], nums[min]);
        }
    }
}

直接選擇排序時間復雜度為：O(n^2)， 雖然都是O(n ^2)，但簡單選擇排序性能略優于冒泡排序，

直接選擇排序空間復雜度為：O(1)，

4.直接插入排序

直接插入排序的基本操作是將未排序好序列的第一個元素插入到已經排好序的序列中，

如：待排序序列為{9，5，1，8，3}，序列長度為5

先來看一次插入程序，黃色為待排序序列，紅色代表已經排序完成的部分，前面4個元素已經排序好了，將最后一個待排元素3插入到排序序列中:

整個排序程序如下：

C++代碼如下：

void insertSort(vector<int> &nums) {
    //設記錄序列長度為n
    //外回圈，插入次數為n - 1次
    for (int i = 0; i < nums.size() - 1; ++i) {
        int end = i;  //end為已排序序列最后一個元素下標
        int temp = nums[i + 1]; //temp用來保存待插入元素
        //內回圈，最多回圈i次
        while (end >= 0) {
            if (nums[end] > temp) {
                nums[end + 1] = nums[end];
                --end;
            } else {
                break;
            }
        }
        nums[end + 1] = temp;
    }
}

直接插入排序時間復雜度為：O(n^2)， 雖然都是O(n ^2)，但直接插入排序性能優于簡單選擇排序和冒泡排序，

直接插入排序空間復雜度為：O(1)，

5.希爾排序

直接插入排序在記錄序列本身就是基本有序或者記錄序列比較短時效率比較高，然而這兩個條件比較苛刻，但是沒有條件我們可以創造條件，

我們可以把待排序序列分為若干個子序列，此時每個子序列的記錄序列就比較短了，對這些子序列分別進行插入排序，當整個序列都基本有序時，對整個序列進行一次直接插入排序，這樣效率就提高了，

希爾排序的思想是，先選定一個小于N的整數gap作為第一增量，將所有距離為gap的元素分在同一組，對每一組元素分別進行插入排序，這樣就能做到基本有序，然后取比N小的gap重復上述操作，直到gap = 1，相當于對整個序列進行了一次直接插入排序，排序完成，

例如：待排序序列為{9，1，5，8，3，7，4，6}，序列長度為8.

整個排序程序如下：

• 令第一增量gap = 8 / 2 = 4，分成4組子序列，對每組子序列分別進行直接插入排序，

• 第二增量gap = 4 / 2 = 2,分成2組子序列，對每組子序列分別進行直接插入排序，

• 第三增量gap = 2 / 2 = 1,相當于對整個序列進行一次直接插入排序，

• 排序完成

C++代碼如下：

void shellSort(vector<int>& nums) {
	int n = nums.size();
	int gap = n;
	while (gap > 1) {
		gap = gap / 2;
		for (int i = 0; i < n - gap; ++i) {
			int end = i;
			int temp = nums[end + gap];
			while (end >= 0) {
				if (nums[end] > temp) {
					nums[end + gap] = nums[end] ;
					end -= gap;
				} else {
					break;
				}
			}
			nums[end + gap] = temp;
		}
	}
}

希爾時間復雜度為：O(n^?)， 終于使得時間復雜度超越了O(n^2)，

直接插入排序空間復雜度為：O(1)，

6.堆排序

6.1大頂堆和小頂堆

堆是具有下列性質的完全二叉樹：

• 每個結點的值都大于等于其左右孩子結點的值，稱為大頂堆
• 每個結點的值都小于等于其左右孩子的值，稱為小頂堆，

如下圖的大頂堆和小頂堆

二叉樹的編號結點具有如下性質，對于任意編號索引大于0的結點，有：

• 父結點的編號索引為：(k - 1) / 2，
• 左孩子的編號索引為：2 × k + 1，
• 右孩子的編號索引為：2 × k + 2，

堆的定義用上面的性質來描述的話，則有：

• 大根堆：arr[k] > arr[2 × k + 1] && arr[k] > arr[2 × k + 2]
• 小根堆：arr[k] < arr[2 × k + 1] && arr[2 × k + 1] < arr[2 × k + 2]

6.2堆排序演算法

堆排序就是利用堆進行排序的方法，升序排序用大頂堆，降序排序用小頂堆， 以升序排序為例，它的基本思想是：

• 將待排序的序列構造成一個大頂堆，此時整個序列的最大值就是堆頂的根結點，
• 將它與堆陣列的末尾元素進行交換，此時末尾元素就是最大值，
• 將除了末尾元素的剩余的n - 1個序列重新構造成一個大頂堆，重復上述步驟，便能得到一個有序序列了，

因此，堆排序演算法主要要解決兩個問題：

1. 如何將無序序列構建成一個堆？
2. 如何在輸出堆頂元素后，調整剩余元素為一個新的堆？

①構造堆

構造堆的主要思路:每插入一個結點都要滿足新的堆為大頂堆，每次新插入的資料都與父結點進行比較，如果插入的數比父節點大，則與父節點交換，否則一直向上交換，直到小于等于父節點，或者來到了頂堆，

例如：待排序序列為{1，5，9，8，3}，序列長度為5,將其構造成一個大頂堆

整個構造程序如下：

• 插入第一個結點為根節點，天然滿足大頂堆要求，

• 插入5，5比父節點1大，則交換兩個結點，

• 插入9，9比父節點5大，則交換2個結點，

• 插入結點8，比父結點1小，交換兩個結點；接著與其父節點9比較，比父結點9小，維持不變，

• 新插入結點3，比其父結點8小，保持不變，

• 一個大頂堆就構建成功了，

然而這種構造方法需要額外的空間來存放堆，那么我們有什么方法可以直接對給定的陣列進行調整成一個堆呢？

②調整一個陣列變成一個堆

如：對vector<int> nums {1, 5, 8, 9, 3}進行調整為一個大頂堆

如果從根節點向下調整，選擇左右孩子中較大的一個交換，那么根節點得出的結果很可能不是最大的值，如上圖，根節點1左右孩子中選擇較大的交換，那么根的值變成8，并不是最大值，

因此，只能從倒數第二層開始向上進行調整， 程序如下：

• 最后一個結點的編號為4，其雙親結點編號（4 - 1） / 2 = 1,對1結點進行調整，5的左右孩子較大的值為9，則與9交換，

  

• 編號1的前一個結點是編號0的結點即根節點，拿頂端的數與其左右孩子較大的數進行比較，如果頂端的數大于左右孩子較大的數，則停止；如果小于左右孩子較大的數，則交換，然后繼續與下面的孩子進行比較，

③固定堆頂元素并將剩余元素重新調整一個堆

主要思路是：將堆頂與最后一個元素進行交換并固定，將其余陣列重新構造成一個大頂堆，即拿頂端的數與其左右孩子較大的數進行比較，如果頂端的數大于左右孩子較大的數，則停止；如果小于左右孩子較大的數，則交換，然后繼續與下面的孩子進行比較，

對上述堆進行重排，程序如下：

• 交換堆頂和最后一個元素進行交換固定9，其余部分重新構成大頂堆，3小于其左右孩子較大的8，交換，3與其左孩子1比，大于1，保持不變，

• 交換堆頂和最后一個元素進行交換固定8，其余部分重新構成大頂堆，1小于其左右孩子較大的5，交換，

• 交換堆頂和最后一個元素進行交換固定5，其余部分重新構成大頂堆，1小于其左孩子3，交換，

• 交換堆頂和最后一個元素進行交換固定3，其余部分重新構成大頂堆，

• 固定根節點，

其C++代碼如下：

//選定的結點與其左右孩子較大的數進行比較，如果選定的結點大于左右孩子較大的數，則停止；如果小于左右孩子較大的數，則交換，然后繼續與下面的孩子進行比較，
void adjust(vector<int> &nums, int i, int len) {
    while (i * 2 + 1 <= len) {
        int leftChild = 2 * i + 1;
        int rightChild = 2 * i + 2;
        int large = 0;
        if (leftChild <= len && nums[leftChild] > nums[i]) {
            large = leftChild;
        } else {
            large = i;
        }
        if (rightChild <= len && nums[rightChild] > nums[large]) {
            large = rightChild;
        }
        if (large != i) {
            swap(nums[i], nums[large]);
            i = large;
        } else {
            break;
        }
    }
}
//從倒數第二層向上建立大頂堆
void buildMaxHeap(vector<int> &nums, int len) {
    for (int i = len / 2; i >= 0; --i) {
        adjust(nums, i, len);
    }
} 
void heapSort(vector<int> &nums) {
    int len = nums.size() - 1;
    buildMaxHeap(nums, len);
    for (int i = len; i >= 1; --i) {
        swap(nums[i], nums[0]);
        len -= 1;
        adjust(nums, 0, len);
    }
}

堆排序時間復雜度為：O(nlogn)，

堆排序空間復雜度為：O(1)，

堆排序是一種不穩定排序，

7.歸并排序

如果我們統計全國收入中位數、最大值等，一般中央都要劃到各個省，各個省又要劃到各個市，各個市又劃到各個街道分開統計各自的一小部分資料，然后逐漸合并到中央，就得到了全國的資料，歸并排序的思想也是如此，

歸并排序的原理是：結社初始序列中含有n個記錄，則可以堪稱n個有序的子序列，每個子序列的長度為1，然后兩兩合并，得到n/2個有序的子序列；再兩兩歸并，…，如此重復，直至得到一個長度為n的有序序列為止，

如：序列{16，7，13，10，9，15，3，2}進行歸并排序，

C++代碼如下：

vector<int> tmp;
void mergeSort(vector<int> &nums, int left, int right) {
    if (left >= right) return;
    int mid = (left + right) / 2;
    mergeSort(nums, left, mid);
    mergeSort(nums, mid + 1, right);
    int i = 1, j = mid + 1;
    int cnt = 0;
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j]) {
            tmp[cnt++] = nums[i++];
        } else {
            tmp[cnt++] = nums[j++];
        }
    }
    while (i <= mid) {
        tmp[cnt++] = nums[i++];
    }
    while (j <= right) {
        tmp[cnt++] = nums[j++];
    }
    for (int i = 0; i < right - 1 + 1; ++i) {
        nums[i + 1] =tmp[i];
    }
}

堆排序時間復雜度為：O(nlogn)，

堆排序空間復雜度為：需要一個臨時空間存放歸并好的區間的資料，

堆排序是一種穩定排序，

8.快速排序

快速排序是對冒泡排序的優化，其基本思想是：通過一趟排序將待排記錄分割成獨立的兩部分，其中一部分記錄的關鍵字比另一部分的關鍵字小，則可分別對這兩部分記錄繼續進行排序，以達到整個序列有序的目的，

具體來說就是選擇一個關鍵字，然后想辦法把它放到一個位置，使得它左邊的關鍵字都比它小，右邊的關鍵字都比它大，這樣的關鍵字我們稱為樞軸（pivot），具體做法如下：

• 選擇一個元素的關鍵字作為key，
• 定義兩個指標left指向第一個元素，right指向最后一個元素，
• right向左尋找小于等于pivot的元素，交換left和right的元素，left向右尋找大于等于pivot的元素，交換left和right的元素，重復這個程序直至left = right,此時位置為pos，
• 對 [0, pos - 1]和[pos + 1, end]分別遞回呼叫快速排序演算法，

從下面的例子來說明，

例：對陣列{50，10，90，30，70，40，80，60，20}進行排序，

程序如下：

• 選取第一個元素50作為pivot，left指向第一個元素，right指向最后一個元素，

• right指向20小于50，調換left和right，

• 接著left向左尋找大于等于50的元素，找到90，交換left和right，

• 接著重復上述程序，right向左尋找小于等于50的元素，找到40，調換left和right，

• left向右尋找大于50的元素，找到70，調換left和right，

• right向左遇到left，此時的位置為pos，

• 接著對[0, pos - 1]和[pos + 1, 7]兩個區間分別進行遞回上述程序，

• 不斷重復上述程序直至排序成功，

C++代碼如下：

//一趟排序將序列劃分成樞軸pivot左右兩部分,并回傳樞軸pivot位置
int partition(vector<int>& nums, int left, int right) {
	int pivot = nums[left];
	while (left <= right) {
		while (left < right && nums[right] >= pivot) {
			--right;
		}
		swap(nums[left], nums[right]);
		while (left < right && nums[left] <= pivot) {
			++left;
		}
		swap(nums[left], nums[right]);
        if (left == right) break;
	}
	return left;
}
//快速排序
void quickSort(vector<int>& nums, int left, int right) {
	if (left < right) {
		int pivot = partition(nums, left, right);
		quickSort(nums, left, pivot - 1);
		quickSort(nums, pivot + 1, right);
	}
}

最優情況下，快速排序時間復雜度為O(nlogn)，

然而，在最壞的情況下，待排序的序列是正序或者倒序，每次劃分只比上次劃分少一個記錄的子序列就變成了斜樹，效率會大大下降，時間復雜度退化為O(n^2)，

這就需要對快速排序進行改進，我們可以隨機取一個關鍵字作為我們的樞軸pivot，

C++代碼如下：

//一趟排序將序列劃分成樞軸pivot左右兩部分,并回傳樞軸pivot位置
int partition(vector<int>& nums, int left, int right) {
	int random = rand() % (right - left + 1) + left;
	int pivot = nums[random];
	while (left <= right) {
		while (left < right && nums[right] >= pivot) {
			--right;
		}
		swap(nums[left], nums[right]);
		while (left < right && nums[left] <= pivot) {
			++left;
		}
		swap(nums[left], nums[right]);
        if (left == right) break;
	}
	return left;
}
//快速排序
void quickSort(vector<int>& nums, int left, int right) {
	if (left < right) {
		int pivot = randPartition(nums, left, right);
		quickSort(nums, left, pivot - 1);
		quickSort(nums, pivot + 1, right);
	}
}

快速排序時間復雜度為：O(nlogn)，

快速排序空間復雜度為：O(1)

快速排序是一種不穩定排序，