<font color=red>說(shuō)明：下述內(nèi)容除了少許圖片選取自他人網(wǎng)站褐墅，其余均為本人獨(dú)創(chuàng)。</font>
0洪己、排序算法導(dǎo)論
排序的概念
??數(shù)據(jù)結(jié)構(gòu)中的一個(gè)重點(diǎn)概念就是內(nèi)部排序妥凳，內(nèi)部排序是指待排序列完全存放在內(nèi)存中所進(jìn)行的排序過(guò)程，適合不太大的元素序列答捕。其功能是對(duì)一個(gè)數(shù)據(jù)元素集合或序列重新排列成一個(gè)按數(shù)據(jù)元素某個(gè)相知有序（遞增逝钥，遞減）的序列。
排序的分類(lèi)
- 插入類(lèi)排序：直接插入排序拱镐、希爾排序艘款。
- 交換類(lèi)排序：冒泡排序、快速排序沃琅。
- 選擇排序：簡(jiǎn)單選擇排序哗咆、堆排序。
- 歸并排序益眉。
- 基數(shù)排序晌柬。
- 桶排序姥份。
- 計(jì)數(shù)排序。
術(shù)語(yǔ)說(shuō)明
- 穩(wěn)定的排序： 排序過(guò)程中有前后兩個(gè)元素相同的點(diǎn)年碘，待排序結(jié)束后澈歉，這兩個(gè)相同的點(diǎn)的相對(duì)前后位置<font color=purple>不發(fā)生</font>變化。
- 不穩(wěn)定的排序： 排序過(guò)程中有前后兩個(gè)元素相同的點(diǎn)屿衅，待排序結(jié)束后埃难，這兩個(gè)相同的點(diǎn)的相對(duì)前后位置<font color=purple>發(fā)生了</font>變化。
- 時(shí)間復(fù)雜度： 一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間傲诵。
- 空間復(fù)雜度：執(zhí)行完一個(gè)程序所需內(nèi)存的大小凯砍。
算法種類(lèi)、時(shí)間復(fù)雜度拴竹、空間復(fù)雜度悟衩、是否穩(wěn)定
out-place：占用額外內(nèi)存。
k：桶的個(gè)數(shù)栓拜。
算法分類(lèi)
<font color=red>注意：本博客涉及到的所有排序算法均是升序排序座泳！</font>
1、直接插入排序
算法描述
??直接插入排序的過(guò)程是最開(kāi)始固定頭一個(gè)元素幕与，然后在第二個(gè)元素開(kāi)始挑势，從前面已經(jīng)排好序的序列中，選擇一個(gè)合適的位置啦鸣，將待插入元素插入到前面排好序的序列中潮饱。方法是從后向前的掃描序列，每掃描一次元素向后移動(dòng)一個(gè)位置诫给。
代碼實(shí)現(xiàn)
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
int i = 1, j = 0;
for(; i < nums.size(); i++){
int tmp = nums[i];
for(j = i; j > 0; j--){
if(tmp < nums[j - 1])
nums[j] = nums[j - 1];
else
break;
}
nums[j] = tmp; // 該賦值語(yǔ)句要寫(xiě)在for循環(huán)的外面香拉，否則當(dāng)待排序元素需要排在第0個(gè)位置時(shí)，無(wú)法正確處理中狂。
}
return nums;
}
};
運(yùn)行截圖
2凫碌、希爾排序
算法描述
??希爾排序也稱(chēng)為縮小增量排序，是直接插入類(lèi)排序的改進(jìn)方法胃榕，時(shí)間復(fù)雜度在盛险。算法思想是每次選一定的增量為一個(gè)分組，在該分組中進(jìn)行直接插入排序勋又。下一輪減小增量苦掘，再使用相同的方法， 直到增量為1為止楔壤，對(duì)全體元素執(zhí)行整體的直接插入排序算法鹤啡。
??嚴(yán)蔚敏的數(shù)據(jù)結(jié)構(gòu)課本中的希爾排序法的增量為：5， 3挺邀， 1揉忘，這也是一般的計(jì)算機(jī)考研中數(shù)據(jù)結(jié)構(gòu)題目中的希爾排序增量。
??下面的代碼中的增量是數(shù)組長(zhǎng)的端铛，隨后依次2倍遞減泣矛。
代碼實(shí)現(xiàn)
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
int len = nums.size(), tmp = 0;
int gap = len / 2;
for(; gap; gap /= 2){
for(int i = gap; i < len; i++){
tmp = nums[i];
int preIndex = i - gap;
while(preIndex >= 0 and nums[preIndex] > tmp){
nums[preIndex + gap] = nums[preIndex];
preIndex -= gap;
}
nums[preIndex + gap] = tmp;
}
}
return nums;
}
};
運(yùn)行截圖
3、冒泡排序
算法描述
??冒泡排序的過(guò)程是從左至右依次比較兩個(gè)相鄰的元素禾蚕，若前面的元素大于后面的元素您朽，則交換兩個(gè)元素，否則不執(zhí)行操作换淆。待指針從左至右遍歷結(jié)束后哗总，數(shù)組中的最大值便被交換到了最右邊，依稀類(lèi)推倍试，直到在某一輪遍歷的過(guò)程中沒(méi)有元素發(fā)生交換為止讯屈。
??由于整個(gè)過(guò)程就像冒泡一樣，所以名為冒泡排序县习。
代碼實(shí)現(xiàn)
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
int i = nums.size() - 1, j = 0;
for(; i > 0; i--){
bool flag = true; // 設(shè)置flag是冒泡排序的優(yōu)化算法
for(j = 0; j < i; j++){
if(nums[j] > nums[j + 1]){
swap(nums[j], nums[j + 1]);
flag = false;
}
}
if(flag)
break;
}
return nums;
}
};
運(yùn)行截圖
4涮母、快速排序
算法描述
??快速排序也是交換類(lèi)排序的一種。思想是通過(guò)設(shè)置一個(gè)點(diǎn)為樞軸（一般為數(shù)組中的第一個(gè)元素）躁愿，通過(guò)一趟排序之后叛本，樞軸位于序列的中部位置，要求樞軸的左邊元素均小于樞軸彤钟，樞軸的右邊元素均大于樞軸来候。再分別遞歸對(duì)樞軸左邊的元素和樞軸右邊的元素執(zhí)行快速排序直到數(shù)列整體有序?yàn)橹埂?/p>
??具體實(shí)現(xiàn)：設(shè)置指針指向序列的最右邊元素，依次從右向左遍歷數(shù)組逸雹，找到第一個(gè)不大于樞軸的元素营搅，將樞軸的值與該值交換，然后再?gòu)淖笙蛴乙来伪闅v數(shù)組找到第一個(gè)不小于樞軸的值峡眶，將樞軸的值與該值交換幽纷，指針再指向右邊沒(méi)有遍歷的位置開(kāi)始遍歷叠洗，方法與上述相同，以此類(lèi)推，直到樞軸處于數(shù)組的中部無(wú)可交換的元素為止椰憋。第一輪快速排序結(jié)束，再分別對(duì)樞軸兩邊的序列遞歸調(diào)用快速排序的方法魏割，直到整體元素有序?yàn)橹埂?/p>
動(dòng)態(tài)圖和下述代碼的樞軸選取略有不符廊勃。
代碼實(shí)現(xiàn)（嚴(yán)蔚敏《數(shù)據(jù)結(jié)構(gòu)》定義樞軸函數(shù)寫(xiě)法）
class Solution {
public:
int partition(vector<int>& nums,int low,int high){
int pivot = nums[low];
while(low < high){
while(low < high and nums[high] >= pivot)
--high;
nums[low] = nums[high];
while(low < high and nums[low] <= pivot)
++low;
nums[high] = nums[low];
}
nums[low] = pivot;
return low;
}
void QuickSort(vector<int>& nums,int low,int high){
if(low < high){
int pivotpos = partition(nums, low, high);
QuickSort(nums, low, pivotpos - 1);
QuickSort(nums, pivotpos + 1, high);
}
}
vector<int> sortArray(vector<int>& nums) { // 主函數(shù)
int n = nums.size();
QuickSort(nums, 0, n - 1);
return nums;
}
};
運(yùn)行截圖
顯然時(shí)間復(fù)雜度要快于上面的希爾排序。
代碼實(shí)現(xiàn)（考研《天勤高分筆記》的寫(xiě)法）
class Solution {
public:
void quickSort(vector<int>& nums, int left, int right) {
if (left >= right)
return;
int cur = left + 1; // 從左側(cè)第二個(gè)元素開(kāi)始
int low = left; // 分界點(diǎn)為第一個(gè)元素
while (cur <= right) {
if (nums[cur] <= nums[left]) { // 交換位置保證low的左側(cè)都是小于num[left]
swap(nums[low + 1], nums[cur]);
low++;
}
cur++;
}
swap(nums[left], nums[low]); // 把分界點(diǎn)元素移動(dòng)到新的分界位置
quickSort(nums, left, low - 1);
quickSort(nums, low + 1, right);
}
vector<int> sortArray(vector<int>& nums) { //主函數(shù)
int n = nums.size();
quickSort(nums, 0, n - 1);
return nums;
}
};
運(yùn)行截圖
5搬男、簡(jiǎn)單選擇排序
算法描述
??簡(jiǎn)單選擇排序是選擇類(lèi)排序拣展，算法思想是從左至右遍歷數(shù)組，首先固定數(shù)組中的第一個(gè)元素缔逛，分別與剩余的所有元素進(jìn)行比較备埃，從而找到序列中的最小值和固定元素交換姓惑，如果固定元素就是最小值，則無(wú)需交換按脚。以此類(lèi)推于毙，直到整體元素有序?yàn)橹埂?/p>
代碼實(shí)現(xiàn)
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
int n = nums.size();
for(int i = 0; i < n; i++){
int m = i;
for(int j = i + 1; j < n; j++){
if(nums[m] > nums[j])
m = j;
}
swap(nums[i], nums[m]);
}
return nums;
}
};
運(yùn)行截圖
6、堆排序
算法描述
??堆排序?qū)儆谶x擇排序辅搬，是簡(jiǎn)單選擇排序的優(yōu)化唯沮。算法思想：排序?yàn)樯颍⒋箜敹选?/p>
- 將數(shù)組中的元素從前向后依次抽象成一個(gè)完全二叉樹(shù)堪遂，并保證根結(jié)點(diǎn)的值大于孩子結(jié)點(diǎn)的值介蛉，它的每棵子樹(shù)保持這個(gè)性質(zhì)。
- 這就需要對(duì)二叉樹(shù)的值進(jìn)行調(diào)整溶褪，最下面最右面的子樹(shù)開(kāi)始币旧，由下到上調(diào)整，如果孩子結(jié)點(diǎn)的值大于父結(jié)點(diǎn)的值猿妈，則將孩子結(jié)點(diǎn)的值和父結(jié)點(diǎn)的值進(jìn)行交換佳恬，以此類(lèi)推，直到滿足上面的性質(zhì)為止于游。
- 此時(shí)最大值存在于根結(jié)點(diǎn)毁葱，將根結(jié)點(diǎn)與最右邊葉子結(jié)點(diǎn)的值進(jìn)行交換，此時(shí)贰剥，整個(gè)序列的最大值被存放在整個(gè)數(shù)組的最右邊倾剿。
- 再將剩余的
個(gè)序列按照從根結(jié)點(diǎn)與其左右孩子比較的方法調(diào)整為大頂堆，再與倒數(shù)第二個(gè)結(jié)點(diǎn)進(jìn)行交換蚌成。
- 循環(huán)上述過(guò)程前痘，直到所有結(jié)點(diǎn)全部有序。
??可見(jiàn)下面的兩幅圖担忧，方法原理都是一樣的芹缔。
算法實(shí)現(xiàn)
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
int len = nums.size();
buildMaxHeap(nums, len); // 構(gòu)建一個(gè)大頂堆 升序排列
return nums;
}
void buildMaxHeap(vector<int>& nums, int len){
//第一個(gè)for循環(huán) 從下到上 調(diào)整為大頂堆
for(int i = len / 2 - 1; i >= 0; i--)
adjustHeap(nums, i, len); // 逐一調(diào)整為大頂堆
for(int i = len - 1; i >= 0; i--){
swap(nums[0], nums[i]); // 交換根結(jié)點(diǎn)和最后的結(jié)點(diǎn) 最大值放在最后
adjustHeap(nums, 0 , i); // 對(duì)剩下的序列從上到下調(diào)整為大頂堆
}
}
// 從上到下 調(diào)整為大頂堆
void adjustHeap(vector<int>& nums, int node, int len){
int left = 2 * node + 1;
int right = 2 * node + 2;
int max = node; // 定義max 存儲(chǔ)某棵子樹(shù)的最大結(jié)點(diǎn)下標(biāo)
if(left < len and nums[left] > nums[max])
max = left; // 存在左孩子 左孩子結(jié)點(diǎn)大于其父結(jié)點(diǎn)
if(right < len and nums[right] > nums[max])
max = right; // 判斷該子樹(shù) 哪一個(gè)結(jié)點(diǎn)大于父結(jié)點(diǎn)
if(max != node){ // 如果真存在子結(jié)點(diǎn)大于父結(jié)點(diǎn)的情況 進(jìn)行交換
swap(nums[max], nums[node]);
adjustHeap(nums, max, len);// 交換后 判斷子樹(shù)結(jié)點(diǎn)是否滿足大頂堆的性質(zhì)
}
}
};
運(yùn)行截圖
7、歸并排序
算法描述
??該算法的是采用分治法（Divide and Conquer）瓶盛。將已有序的子序列合并最欠，得到完全有序的序列；
- 先使每個(gè)子序列有序惩猫，再使子序列段間有序芝硬。在嚴(yán)蔚敏《數(shù)據(jù)結(jié)構(gòu)與算法》課本中，將兩個(gè)有序表合并成一個(gè)有序表轧房，稱(chēng)為2-路歸并排序拌阴。
- 把長(zhǎng)度為
的序列分成兩個(gè)長(zhǎng)度為
的子序列；
- 對(duì)這兩個(gè)子序列使用遞歸分別再采用歸并排序奶镶；
-
將兩個(gè)排序好的子序列合并成一個(gè)最終的排序序列迟赃。
在這里插入圖片描述
2-路歸并排序動(dòng)態(tài)圖：
代碼實(shí)現(xiàn)
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
int n = nums.size();
MergeSort(nums, 0, n - 1);
return nums;
}
void MergeSort (vector<int>& nums, int low,int high) {
if(low >= high)
return; // 終止遞歸的條件陪拘，子序列長(zhǎng)度為1
int mid = low + (high - low) / 2; // 取得序列中間的元素
MergeSort(nums, low, mid); // 對(duì)左半邊遞歸
MergeSort(nums, mid + 1, high); // 對(duì)右半邊遞歸
Merge(nums, low, mid, high); // 合并
}
void Merge(vector<int>& nums, int low, int mid, int high){
//low為第1有序區(qū)的第1個(gè)元素，i指向第1個(gè)元素, mid為第1有序區(qū)的最后1個(gè)元素
int i = low,j = mid + 1, k = 0; //mid+1為第2有序區(qū)第1個(gè)元素纤壁，j指向第1個(gè)元素
int *temp = new int[high - low + 1]; //temp數(shù)組暫存合并的有序序列
while(i <= mid && j <= high){
if(nums[i] <= nums[j]) //較小的先存入temp中
temp[k++] = nums[i++];
else
temp[k++] = nums[j++];
}
while(i <= mid)//若比較完之后藻丢，第一個(gè)有序區(qū)仍有剩余，則直接復(fù)制到t數(shù)組中
temp[k++] = nums[i++];
while(j <= high)//同上
temp[k++] = nums[j++];
for(i=low, k=0; i <= high; i++,k++)//將排好序的存回arr中l(wèi)ow到high這區(qū)間
nums[i] = temp[k];
delete [] temp;//釋放內(nèi)存摄乒，由于指向的是數(shù)組，必須用delete []
}
};
運(yùn)行截圖
8残黑、基數(shù)排序
算法描述
??基數(shù)排序是非比較的排序算法馍佑，對(duì)每一位進(jìn)行排序，從最低位開(kāi)始排序梨水，復(fù)雜度為O(kn)為數(shù)組長(zhǎng)度拭荤，k為數(shù)組中的數(shù)的最大的位數(shù)；
- 基數(shù)排序是按照低位先排序疫诽，然后收集舅世；
- 再按照高位排序，然后再收集奇徒；
- 以此類(lèi)推雏亚，直到最高位。
??有時(shí)候有些屬性是有優(yōu)先級(jí)順序的摩钙，先按低優(yōu)先級(jí)排序罢低，再按高優(yōu)先級(jí)排序。最后的次序就是高優(yōu)先級(jí)高的在前胖笛，高優(yōu)先級(jí)相同的低優(yōu)先級(jí)高的在前网持。基數(shù)排序基于分別排序长踊，分別收集功舀，所以是穩(wěn)定的。
代碼實(shí)現(xiàn)（java實(shí)現(xiàn)身弊，只允許有非負(fù)數(shù)）
class Solution {
public int[] sortArray(int[] nums) {
if (nums.length < 2)
return array;
int max = nums[0];
for (int i = 1; i < nums.length; i++) {
max = Math.max(max, nums[i]);
}
int maxDigit = 0;
while (max != 0) {
max /= 10;
maxDigit++;
}
int mod = 10, div = 1;
ArrayList<ArrayList<Integer>> bucketList = new ArrayList<ArrayList<Integer>>();
for (int i = 0; i < 10; i++)
bucketList.add(new ArrayList<Integer>());
for (int i = 0; i < maxDigit; i++, mod *= 10, div *= 10) {
for (int j = 0; j < nums.length; j++) {
int num = (nums[j] % mod) / div;
bucketList.get(num).add(nums[j]);
}
int index = 0;
for (int j = 0; j < bucketList.size(); j++) {
for (int k = 0; k < bucketList.get(j).size(); k++)
nums[index++] = bucketList.get(j).get(k);
bucketList.get(j).clear();
}
}
return nums;
}
}
9辟汰、計(jì)數(shù)排序
算法描述
??計(jì)數(shù)排序的過(guò)程是創(chuàng)建一個(gè)長(zhǎng)度為數(shù)組中最小和最大元素之差的數(shù)組，分別對(duì)應(yīng)數(shù)組中的每個(gè)元素阱佛，然后用這個(gè)新的數(shù)組來(lái)統(tǒng)計(jì)每個(gè)元素出現(xiàn)的頻率莉擒，然后遍歷新的數(shù)組，根據(jù)每個(gè)元素出現(xiàn)的頻率把元素放回到老的數(shù)組中瘫絮，得到已經(jīng)排好序的數(shù)組涨冀。
代碼實(shí)現(xiàn)
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
if (nums.size() == 0)
return nums;
int min = *min_element(nums.begin(), nums.end());
int max =*max_element(nums.begin(), nums.end());
int bias = 0 - min;
vector<int> bucket(max - min + 1, 0);
for (int i = 0; i < nums.size(); i++) {
bucket[nums[i] + bias]++;
}
int index = 0, i = 0;
while (index < nums.size()) {
if (bucket[i] != 0) {
nums[index] = i - bias;
bucket[i]--;
index++;
} else
i++;
}
return nums;
}
};
運(yùn)行截圖
??該方法通過(guò)犧牲空間復(fù)雜度的方法換取時(shí)間復(fù)雜度的減少，是目前在LeetCode平臺(tái)上這些算法中運(yùn)行最快的方法麦萤。
??當(dāng)然鹿鳖，該方法也可以通過(guò)哈希表來(lái)實(shí)現(xiàn)扁眯。
代碼實(shí)現(xiàn)（map哈希表方法）
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
map<int, int> m;
for(int& i : nums)
m[i]++;
int n = nums.size(), i = 0;
while(i < n){
if(m.begin()->second){
nums[i++] = m.begin()->first;
m.begin()->second--;
}
else
m.erase(m.begin());
}
return nums;
}
};
運(yùn)行截圖
??上述代碼的思路就是計(jì)數(shù)排序，但使用哈希表翅帜，時(shí)間復(fù)雜度大為增加姻檀，這值得引人思考。
10涝滴、桶排序
算法描述
??首先新建一個(gè)桶的數(shù)組绣版，每個(gè)桶的規(guī)則需要提前制定好，比如元素在為一個(gè)桶歼疮、
為一個(gè)桶杂抽。然后遍歷整個(gè)待排序的數(shù)組，把元素分配到對(duì)應(yīng)的桶里面韩脏。接下來(lái)單獨(dú)對(duì)每個(gè)桶里面的元素進(jìn)行排序缩麸，排序算法可以選擇比較排序或者非比較排序，得到排序后的數(shù)組赡矢。最后把所有的桶內(nèi)的元素還原到原數(shù)組里面得到最后的排序數(shù)組杭朱。
代碼實(shí)現(xiàn)
class Solution {
public int[] sortArray(int[] nums) {
int INTERVAL = 100; // 定義桶的大小
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
for (int num : nums) { // 找到數(shù)組元素的范圍
min = Math.min(min, num);
max = Math.max(max, num);
}
int count = (max - min + 1); // 計(jì)算出桶的數(shù)量
int bucketSize = (count % INTERVAL == 0) ?( count / INTERVAL) : (count / INTERVAL+1);
List<Integer>[] buckets = new List[bucketSize];
for (int num : nums) { // 把所有元素放入對(duì)應(yīng)的桶里面
int quotient = (num-min) / INTERVAL;
if (buckets[quotient] == null) buckets[quotient] = new ArrayList<>();
buckets[quotient].add(num);
}
int cur = 0;
for (List<Integer> bucket : buckets) {
if (bucket != null) {
bucket.sort(null); // 對(duì)每個(gè)桶進(jìn)行排序
for (Integer integer : bucket) { // 還原桶里面的元素到原數(shù)組
nums[cur++] = integer;
}
}
}
return nums;
}
}
運(yùn)行截圖
總結(jié)
??通過(guò)上述數(shù)據(jù)結(jié)構(gòu)十大算法的講解和LeetCode系統(tǒng)的運(yùn)行，時(shí)間復(fù)雜度在級(jí)別的顯示超時(shí)吹散，只有時(shí)間復(fù)雜度稍低的才會(huì)顯示通過(guò)弧械。在上述過(guò)程中運(yùn)行最快的是計(jì)數(shù)排序，它是通過(guò)犧牲空間復(fù)雜度來(lái)?yè)Q取的高效運(yùn)行空民，其次是快速排序梦谜，快速排序的空間復(fù)雜度的消耗也相對(duì)比較大，但小于計(jì)數(shù)排序袭景。
??綜合比較唁桩，每個(gè)排序算法各有其特點(diǎn)，不同的排序算法適應(yīng)與不同的場(chǎng)景耸棒。
