排序： 1、排序在電腦數據處理中經常遇到，在日常的數據處理中，一般可以認為有 1/4 的時間用在排序上，而對於程式安裝， 多達 50% 的時間花費在對錶的排序上。簡而言之，排序是將一組雜亂無章的數據按一定的規律順次排列起來 2、內排與外排：根據排序方法在排序過程中數據元素是否完全在記憶體而劃分，若一 ...
排序：
1、排序在電腦數據處理中經常遇到，在日常的數據處理中，一般可以認為有 1/4 的時間用在排序上，而對於程式安裝，
多達 50% 的時間花費在對錶的排序上。簡而言之，排序是將一組雜亂無章的數據按一定的規律順次排列起來
2、內排與外排：根據排序方法在排序過程中數據元素是否完全在記憶體而劃分，若一部分數據在外存，則為外排，否則，為內排
3、排序演算法的穩定性：根據排序後相同元素順序是否會發生改變而定，
如兩個數 a 與 b，a == b 且 a 在 b 的前面，若排序後 a 仍然在 b 的前面，則為穩定的，否則，為不穩定的
4、排序演算法的性能評估：演算法的執行時間是衡量演算法好壞的最重要參數，其時間開銷可用演算法執行中的數據比較次數與移動次數來衡量
排序演算法：
1、時間複雜度：
a、平方階 (O(n2)) 排序 各類簡單排序：直接插入、直接選擇和冒泡排序
b、線性對數階 (O(nlog2n)) 排序：快速排序、堆排序和歸併排序
c、O(n1+§)) 排序，§ 是介於 0 和 1 之間的常數：希爾排序
d、線性階 (O(n)) 排序：基數排序，桶排序和計數排序
2、穩定性：
a、穩定的排序演算法：冒泡排序、插入排序、歸併排序、計數排序、桶排序和基數排序
b、不是穩定的排序演算法：選擇排序、快速排序、希爾排序、堆排序
註：穩定性是相對的，例如我們把比較冒泡排序里對兩個元素比較的演算法改成大於等於，它會變成不穩定的！
3、比較與非比較：
a、比較排序：冒泡排序、插入排序、希爾排序、選擇排序、快速排序、歸併排序和堆排序
b、非比較排序：計數排序、桶排序和基數排序
十大經典排序演算法：
以下均按非降序排序
1、冒泡排序(bubbleSort)：
a、比較相鄰兩個元素，若前者的大於後者，則交換這兩個元素
b、向後移動一項，再執行比較交換操作；當移動到最後一位時，這個元素即為本輪最大值
c、從新從頭開始，除了最後一項，執行 a、b 操作，直到排序完成
註：在排序過程中，我們可以設置一個標誌判斷在一輪排序中是否有交換元素，若一輪排序過後仍無交換，則說明排序已完成
#include <iostream> #include <vector> #include <cstdlib> //採用引用的方式傳參，否則傳入的只是一個不會改變原數據的形參 void bubbleSort(std::vector<int>& nums); int main() { std::vector<int> nums; int len = 0; std::cout<<"請輸入長度："; do { std::cin>>len; if (len <= 0) // 標準錯誤流，輸出錯誤信息 std::cerr<<"請輸入正整數："; } while (len <= 0); int num = 0; std::cout<<"輸入 "<<len<<" 個數: "; // size_t 是 unsigned_int 類型，建議在使用下標時使用，但若將負數賦值給它，則會將該數轉換為正數，從而產生錯誤 for (size_t i = 0; i < len; ++i) { std::cin>>num; nums.push_back(num); } bubbleSort(nums); std::cout<<"排序後的數組："; // 自由 for 迴圈 for (int num : nums) // std::ends 輸出空白符，不同電腦的空白符可能不一樣 std::cout<<num<<std::ends; std::cout<<std::endl; system("pause"); return 0; } void bubbleSort(std::vector<int>& nums) { // 設置交換標誌，若一次迴圈後所有元素都未發生交換，則說明數組已經排列好，可提前退出 bool exchange = false; size_t len = nums.size(); for (size_t i = 1; i < len; ++i) { exchange = false; // 為了方便，我把最小的元素移動到了最前 for (size_t j = len-1; j >= i; j--) { if (nums[j-1] > nums[j]) { int temp = nums[j-1]; nums[j-1] = nums[j]; nums[j] = temp; exchange = true; } } if (!exchange) return; } }View Code
2、選擇排序(selectionSort)：
a、在初始序列 R[i...n-1] 中找到最小的元素，放到 R[i] 處，i=0，n=待排對象大小
b、++i
c、重覆執行 a、b 操作，直至第 n-1 輪
void selectionSort(std::vector<int>& nums) { size_t len = nums.size(); // 在每次迴圈里選出最小的一個排在前面 for (size_t i = 0; i < len-1; ++i){ int min = i; for (size_t j = i+1; j < len; ++j){ if (nums[j] < nums[min]) min = j; } if (i != min){ int temp = nums[i]; nums[i] = nums[min]; nums[min] = temp; } } return ; }View Code
3、簡單插入排序(insertionSort)：
a、從第一個元素開始，該元素可以認為已經被排序
b、取出下一個元素，在已經排序的元素序列中從後向前掃描
c、如果該元素大於新元素，將該元素移到下一位置
d、重覆操作 c，直到找到已排序的元素小於或等於新元素的位置
e、將新元素插入到該位置後
f、重覆操作 b-e
void insertionSort(std::vector<int>& nums) { size_t len = nums.size(); for (size_t i = 1; i < len; i++) { int temp = nums[i]; // 在迴圈中把較大的數往後移一位 size_t j = i; while (j > 0 && temp < nums[j-1]) { nums[j] = nums[j-1]; j--; } if (j != i) nums[j] = temp; } return ; }View Code
4、希爾排序(shellSort)：
a、設對象有 n 個元素，先取整數 gap < n 作為間隔，並將全部元素分為 gap 個子序列，所有距離為 gap 的元素放在同一子序列中，
在每個子序列中分別施行直接插入排序
b、縮小間隔 gap，如 gap = gap/3 + 1
c、重覆 a、b 操作，直到取 gap == 1 為
註：gap 有多種取法，但如果 gap = n/2 或 gap = gap/2 時，只有到最後一步奇數位置才會和偶數位置的數進行比較
void shellSort(std::vector<int>& nums) { int gap = 1, len = nums.size(); // 先讓間隔 gap 儘量大 while (gap < len) gap = gap*3+1; while (gap > 0){ for (int i = gap; i < len; i++){ int temp = nums[i]; int j = i - gap; // 直接插入排序 while (j >= 0 && nums[j] > temp){ nums[j+gap] = nums[j]; j -= gap; } nums[j+gap] = temp; } gap /= 3; } return ; }View Code
5、快速排序(quickSort)：
a、從數列中挑出一個元素，稱為 “基準”（一般為第一個元素）
b、重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）。
在這個分區退出之後，該基準就處於數列的中間位置。這個稱為分區（partition）操作
c、遞歸地把小於基準值元素的子數列和大於基準值元素的子數列排序
註：快排的非遞歸演算法可以使用棧來實現
void QuickSort(int* arr, int low, int high) { int star = low, end = high; if (star > end) return ; int temp = arr[star]; while (star != end) { // 從後找出小於“基準”的數 while (arr[end] >= temp && star < end) end--; // 從前找出大於“基準”的數 while (arr[star] <= temp && star < end) star++; // 若還在範圍內，則交換這兩者 if (star < end) { int t = arr[star]; arr[star] = arr[end]; arr[end] = t; } } // 把“基準”移動到“中間” int t = arr[low]; arr[low] = arr[star]; arr[star] = t; // 遞歸 QuickSort(arr, low, star-1); QuickSort(arr, star+1, high); return ; }View Code
