文章目錄
- 前言
- 交集排序
- 冒泡
- 簡單
- 快速排序
- 插入排序
- 直接插入排序
- 希爾排序
- 選擇排序
- 簡單選擇排序
- 堆排序
- 歸并排序
- 二路
- 多路
- 非比較類
- 計數排序
- 桶排序
- 基數排序
- 最后
前言
兄弟們，應上篇資料結構的各位要求，今天我開始作業了，開始肝演算法，劍指offer還在路上，我真想開車去接它，奈何碼神沒有駕照的開車，算了，弄排序演算法吧，有點長，耐心看啊，原創不易，你們懂的，先上一張圖
可以看出排序演算法，還是比較多的，算了，不多說了，你我肝完就是出門自帶4年實習經驗的！
交集排序
冒泡
冒泡我一般也將它稱為列舉就是把所有都走一遍嘛，效率比較低，一般在演算法競賽中如果實在沒有比較好的，可以用，那就先講一個簡單的列舉吧！
列舉字典序
首先可能有的同學不知道什么是字典序，請看：
（1，2，3），（1，3，2）…這就是字典序的體現，官方解釋是這樣的：
字典排序（lexicographical order）是一種對于隨機變數形成序列的排序方法，其方法是，按照字母順序，或者數字小大順序，由小到大的形成序列，
比如說有一個隨機變數X包含{1 2 3}三個數值，
其字典排序就是{1 2 3} {1 3 2} {2 1 3} {2 3 1} {3 1 2} {3 2 1}
如果是字母：先比較第一個字符i和b，b<i，b是第2個，i是第9個2<9于是baray<ilove如果第一位相同，就比較第二位，
例如：abcdd<abcde aaaay<aaaaz如果其中之一是另一個的前綴，則短的那個排前面：aaa
下面用代碼實作一下1-n的排列：
//冒泡排序，我也將它稱為列舉
#include<iostream>
#include<cstdio>
using namespace std;
void print(int n, int *a, int cur)
{
if (cur == n)//遞回邊界
{
for (int i = 0; i < n; i++)
{
printf("%d", a[i]);
}
printf("\n");
}
else for (int i = 1; i <= n; i++)
{
int OK = 1;
for (int j = 0; j < cur; j++)
{
if (a[j] == i)//判斷i是否出現過
OK = 0;
if (OK)//i沒有出現過下一個
{
a[cur] = i;
print(n, a, cur + 1);//遞回
}
}
}
}
int main()
{
}
下面我們來看一下正宗的冒泡排序，總體思想是：倆倆比較，如果反序交換，直到沒有反序的記錄為止，代碼實作比較簡單，是倆個for回圈的嵌套
#include<iostream>
#include<algorithm>//呼叫演算法庫，使用交換函式swap
#include<cstdio>
using namespace std;
int main()
{
int a[10];
for (int i = 0; i < 10; i++)
{
cin >> a[i];
}
for (int i = 0; i < 10; i++)
{
for (int j = i + 1; j < 10; j++)
{
if (a[i] < a[j])
swap(a[i], a[j]);
}
}
for (int i = 0; i < 10; i++)
{
printf("%d ", a[i]);
}
return 0;
}
總體來說比較簡單，但是耗時，耗記憶體，反正就是不好，來優化一下，為什么不好？歸根結底還是做了許多重復的運算，大量的比較，
總體思路是這樣的：再某一次比較后，發現所有的資料都變成了順序，直接退出回圈，不再繼續回圈
//將for改為
bool flag = true;
for (int i = 0; i < 10 && flag; i++)
{
flag = false;
for (int j = 10 - 1; j >= i; j--)
{
if (a[j] > a[i])
{
swap(a[j], a[j + 1]);
flag = true;
}
}
}
演算法復雜度：倆個for，就是O（n^2)了，有點大
簡單
選擇排序
先來和冒泡排序比較一下，他倆的主要區別就是冒泡排序的資料在不斷的交換，而快速排序先交換資料的別名，再交換本身，打個比喻就是，一個是幻想天上掉餡餅，背水一戰，的炒股短線選手，而另一個則是看中時機的炒股老手，俗稱股神，
好了，比較也比較完了，我們來看簡單的代碼實作吧
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int main()
{
int a[10];
for (int i = 0; i < 10; i++)
{
cin >> a[i];
}
for (int i = 0; i < 10; i++)
{
int min = i;
for (int j = i + 1; j < 10; j++)
{
if (a[min] > a[j])
min = j;//交換下標位置
}
if (i != min)
swap(a[i], a[min]);
}
for (int i = 0; i < 10; i++)
{
printf("%d ", a[i]);
}
return 0;
}
如果來分析演算法復雜度的話，你會驚訝的發現時間復雜度仍舊是O（n^2)，但是我要說的是它仍舊優于冒泡排序，why？
冒泡排序和選擇排序是排序演算法中比較簡單和容易實作的演算法，冒泡排序的思想為：每一次排序程序，通過相鄰元素的交換，將當前沒有排好序中的最大（小）移到陣列的最右（左）端，而選擇排序的思想也很直觀：每一次排序程序，我們獲取當前沒有排好序中的最大（小）的元素和陣列最右（左）端的元素交換，回圈這個程序即可實作對整個陣列排序，
選擇排序的平均時間復雜度比冒泡排序的稍低:
同樣資料的情況下，2種演算法的回圈次數是一樣的，但選擇排序只有0到1次交換，而冒泡排序只有0到n次交換
快速排序
和冒泡排序相似，但是優于冒泡，總體是一個分治的思想，交換軸點元素
- 劃分：將陣列中的元素都重排分成左右倆部分，使得左邊都小于等于右邊的任意元素
- 遞回求解：把左右分別進行排序
- 合并：這時你會發現已經排列好了
還是排列一串數字，進行代碼實作：
#include<iostream>
using namespace std;
void quickSort(int *arr,int begin,int end)
{
//begin為左，end為右
//如果區間不只一個數
if(begin < end)
{
int temp = arr[begin]; //將區間的第一個數作為基準數
int i = begin; //從左到右進行查找時的“指標”，指示當前左位置
int j = end; //從右到左進行查找時的“指標”，指示當前右位置
//不重復遍歷
while(i < j)
{
//當右邊的數大于基準數時，略過，繼續向左查找
//不滿足條件時跳出回圈，此時的j對應的元素是小于基準元素的
while(i<j && arr[j] > temp)
j--;
//將右邊小于等于基準元素的數填入右邊相應位置
arr[i] = arr[j];
//當左邊的數小于等于基準數時，略過，繼續向右查找
//(重復的基準元素集合到左區間)
//不滿足條件時跳出回圈，此時的i對應的元素是大于等于基準元素的
while(i<j && arr[i] <= temp)
i++;
//將左邊大于基準元素的數填入左邊相應位置
arr[j] = arr[i];
}
//將基準元素填入相應位置
arr[i] = temp;
//此時的i即為基準元素的位置
//對基準元素的左邊子區間進行相似的快速排序
quickSort(arr,begin,i-1);
//對基準元素的右邊子區間進行相似的快速排序
quickSort(arr,i+1,end);
}
//如果區間只有一個數，則回傳
else
return;
}
int main()
{
int num[12] = {23,45,17,11,13,89,72,26,3,17,11,13};
int n = 12;
quickSort(num,0,n-1);
cout << "排序后的陣列為：" << endl;
for(int i=0;i<n;i++)
cout << num[i] << ' ';
cout << endl;
return 0;
}
算一下復雜度吧，最壞O（n^2），平均O（nlogn）幾乎沒有最壞的情況發生，所以效率還是比較高的，想一想如果就只要最大的值怎么弄？
#include<iostream>
using namespace std;
int Partition(int *a, int i, int j)
{
int tmp = a[j];
int index = i;
if (i < j)
{
for (int k = i; k < j; k++) {
if (a[k] >= tmp) {
swap(a[index++], a[k]);
}
}
swap(a[index], a[j]);
return index;
}
}
int Search(int a[], int i, int j, int k)
{
int m = Partition(a, i, j);
if (k == m - i + 1) return a[m];
else if (k < m - i + 1)
{
return Search(a, i, m - 1, k);
}
//后半段
else
{
//核心后半段：再找第 k-(m-i+1)大的數就行
return Search(a, m + 1, j, k - (m - i + 1));
}
}
int main()
{
int a[7] = { 8,7,6,1,2,3,4 };
int k = 3;
cout << Search(a, 2, 6, k);
}
插入排序
直接插入排序
話說，碼神最近在玩斗地主，你們說手機斗地主和真人斗地主最大的區別，或者是說好處是什么？我感覺就是在手機上不用插牌了，省時間，這利用的就是插入排序的原理，可以說是“斗地主排序”
基本操作：將一個記錄插入到已經排好的有序表中，從而得到一個新的，記錄資料+1的有序表
基操，看代碼：
void insertionSort(int *arr, int len) {
if (len<2) {
return ;
}
for (int i=1; i<len; i++) {
int insertValue = arr[i];//暫存需要插入元素
int j = i-1;
//從右向左比較元素
for (; j>=0 && insertValue<array[j]; j--) {
arr[j+1] = arr[j];
}
arr[j+1] = insertValue;
}
}
老規矩，分析時間復雜度，最好的情況是順序都是排列好的，此時只需要比較，時間復雜度為O（n），最壞的情況為O（n^2),平均下來是n ^ 2/4，所以平均時間復雜度也是O（n ^ 2).
希爾排序
如果說誰是第一個將排序演算法復雜度突破O（n^2)的，那么我想希爾是第一個，可以說希爾排序是對插入排序的改進，區別在于，希爾排序可以說是一個不斷分組的排序
先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序，具體演算法描述：
選擇一個增量序列t1，t2，…，tk，其中ti>tj，tk=1；
按增量序列個數k，對序列進行k 趟排序；
每趟排序，根據對應的增量ti，將待排序列分割成若干長度為m 的子序列，分別對各子表進行直接插入排序，僅增量因子為1 時，整個序列作為一個表來處理，表長度即為整個序列的長度，
實作如下：
//希爾排序
void ShellSort(int* arr, int n)
{
int gap = n;
while (gap>1)
{
//每次對gap折半操作
gap = gap / 2;
//單趟排序
for (int i = 0; i < n - gap; ++i)
{
int end = i;
int tem = arr[end + gap];
while (end >= 0)
{
if (tem < arr[end])
{
arr[end + gap] = arr[end];
end -= gap;
}
else
{
break;
}
}
arr[end + gap] = tem;
}
}
}
時間復雜度，牛逼的人們，通過大量的計算發現是O（n^3/2)，小于O
（n^2)，由于是跳躍式的排序所以不是穩定排序
選擇排序
簡單選擇排序
可參考上面
堆排序
何為堆，如果已經學過堆的話，就是那個堆，與堆疊相對的堆，
基本思路：將代排的序列構造成一個大堆，此時，整個序列的最大值就是堆頂的根結點，將它移走，也就是將其與堆陣列的末尾元素交換，此時末尾元素就是最大值，然后將剩余的n-1個序列重新構造成一個堆，這樣就會得到n個元素的次最大值，如此遞回反復就會得到一個有序序列
varlen; // 因為宣告的多個函式都需要資料長度，所以把len設定成為全域變數
function buildMaxHeap(arr) { // 建立大頂堆
len = arr.length;
for(vari = Math.floor(len/2); i >= 0; i--) {
heapify(arr, i);
}
}
function heapify(arr, i) { // 堆調整
varleft = 2 * i + 1,
right = 2 * i + 2,
largest = i;
if(left < len && arr[left] > arr[largest]) {
largest = left;
}
if(right < len && arr[right] > arr[largest]) {
largest = right;
}
if(largest != i) {
swap(arr, i, largest);
heapify(arr, largest);
}
}
function swap(arr, i, j) {
vartemp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
function heapSort(arr) {
buildMaxHeap(arr);
for(vari = arr.length - 1; i > 0; i--) {
swap(arr, 0, i);
len--;
heapify(arr, 0);
}
return arr;
}
時間可以說是主要耗在了初始建堆和在重建堆的反復篩選上
1.構造堆：O（n）
2.重建堆：完全二叉樹：資料結構，詳解時間復雜度為O(nlogn)
又因為堆排序對原始記錄的排序狀態并不敏感，因此它無論是好是壞，時間復雜度都為O（nlogn)，同希爾排序，都為不穩定性的排序
歸并排序
完全二叉樹，是一棵神奇的樹，可以說歸并排序是完全體現了完全二叉樹的性質
二路
若將兩個有序表合并成一個有序表，稱為2-路歸并，
- 把長度為n的輸入序列分成兩個長度為n/2的子序列；
- 對這兩個子序列分別采用歸并排序；
- 將兩個排序好的子序列合并成一個最終的排序序列，
#include<iostream>
using namespace std;
void Merge(int[], int, int[], int, int, int)
void MergeSort(int numbers[], int length, int temp[], int begin, int end)
{
//1. 同樣判斷傳入的引數是否有效
if (numbers == nullptr || length <= 0 || begin < 0 || end >= length)
throw new exception("Invalid input.");
//2. 作為遞回的結束條件，開始下標和結束下標相等時，說明子序列中只有一個元素，看作有序的
if (end - begin == 0)
return;
//3. 定義中間變數，將陣列分半【如果有7個元素，下標0-6，則middle=3，陣列分為長度為4和3的兩段】
int middle = ((end - begin) / 2 ) + begin;
//4. 遞回，先遞回左半邊，再遞回右半邊，將左右子序列不斷分為長度為1的子序列才停止遞回
MergeSort(numbers, length, temp, begin, middle);
MergeSort(numbers, length, temp, middle + 1, end);
//5. 再慢慢歸并
Merge(numbers, length, temp, begin, end, middle);
}
void Merge(int numbers[], int length, int temp[], int begin, int end, int middle)
{
//1. 判斷是否有不符合要求的引數傳入，有則拋出錯誤
if (numbers == nullptr || length <= 0 || begin < 0 || end >= length)
throw new exception("Invalid input.");
//2. 將原序列從中分開
int leftIndex = begin; //左邊序列的開始（左邊序列的結尾是middle）
int rightIndex = middle + 1;//右邊序列的開始（右邊序列的結尾是end）
int tempIndex = begin; //輔助陣列的下標
//3. 當左右子序列尚未到頭時，回圈
while (leftIndex <= middle && rightIndex <= end)
{
//4. 兩兩對比判斷，誰大誰就放入輔助陣列，同時指標后移
if (numbers[leftIndex] < numbers[rightIndex])
temp[tempIndex] = numbers[leftIndex++];
else
temp[tempIndex] = numbers[rightIndex++];
//5. 輔助陣列下標++
++tempIndex;
}
//6. 當左邊或右邊子序列尚未到頭時，直接放入輔助陣列
while (leftIndex <= middle)
temp[tempIndex++] = numbers[leftIndex++];
while (rightIndex <= end)
temp[tempIndex++] = numbers[rightIndex++];
//7. 再將輔助陣列中已經有序的元素覆寫掉原陣列中無序的元素，使原陣列變成部分有序
for (int i = begin; i <= end; ++i)
numbers[i] = temp[i];
}
int main(int arvc, char* argv[])
{
const int length = 9;
int nums[length] = { 18, 7, 23, 3, 9, 32, 10 , 99, 0};
int *temp = new int[length];
MergeSort(nums, length, temp, 0, 8);
for (int i = 0; i < length; i++)
cout << nums[i] << " ";
delete[] temp;
temp = nullptr;
cout << endl;
return 0;
}
多路
同理，將多個有序表合并，稱為多路歸并，和二路歸并幾乎一樣，就不贅述了，
非比較類
計數排序
計數排序不是基于比較的排序演算法，其核心在于將輸入的資料值轉化為鍵存盤在額外開辟的陣列空間中， 作為一種線性時間復雜度的排序，計數排序要求輸入的資料必須是有確定范圍的整數，
- 找出待排序的陣列中最大和最小的元素；
- 統計陣列中每個值為i的元素出現的次數，存入陣列C的第i項；
- 對所有的計數累加（從C中的第一個元素開始，每一項和前一項相加；
- 反向填充目標陣列：將每個元素i放在新陣列的第C(i)項，每放一個元素就將C(i)減去1，
#include <iostream>
using namespace std;
const int MAXN = 1000;
int arr[MAXN];
void counting_sort(int n)
{
int min_value = 0x3f3f3f3f, max_value = 0;
for (int i = 0; i < n; i++)
{
if (arr[i] > max_value)
max_value = arr[i];
if (arr[i] < min_value)
min_value = arr[i];
}
int len = max_value - min_value + 1;
int* bucket = new int[len]();
for (int i = 0; i < n; i++)
{
bucket[arr[i] - min_value]++;
}
for (int i = 0, j = 0; i < len; i++)
{
while (bucket[i] != 0)
{
arr[j++] = i + min_value;
bucket[i]--;
}
}
delete bucket;
}
int main()
{
int n;
cout << "請輸入陣列中元素的個數：";
cin >> n;
cout << "請輸入元素: " << endl;
for (int i = 0; i < n; i++)
{
cin >> arr[i];
}
cout << "排序前：" << endl;
for (int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
cout << endl;
counting_sort(n);
cout << "排序后：" << endl;
for (int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
時間復雜度是O(n+k)，空間復雜度也是O(n+k)，其排序速度快于任何比較排序演算法，當k不是很大并且序列比較集中時，計數排序是一個很有效的排序演算法，
桶排序
桶排序是計數排序的升級版，它利用了函式的映射關系，高效與否的關鍵就在于這個映射函式的確定，桶排序 (Bucket sort)的作業的原理：假設輸入資料服從均勻分布，將資料分到有限數量的桶里，每個桶再分別排序（有可能再使用別的排序演算法或是以遞回方式繼續使用桶排序進行排），
- 設定一個定量的陣列當作空桶；
- 遍歷輸入資料，并且把資料一個一個放到對應的桶里去；
- 對每個不是空的桶進行排序；
- 從不是空的桶里把排好序的資料拼接起來，
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 1000;
const int BUCKET_SIZE = 10;//默認每個桶的范圍
int arr[MAXN];
void insert_sort(vector<int> &v){
int len=v.size(),temp,i,j;
for(i=1;i<len;i++){
temp = v[i];
for(j=i;j>0 && v[j-1]>temp;j--){
v[j]=v[j-1];
}
v[j]=temp;
}
}
void bucket_sort(int n){
int min_value = 0x3f3f3f3f, max_value = 0;
for (int i = 0; i < n; i++)
{
if (arr[i] > max_value)
max_value = arr[i];//獲取輸入資料的最大值
if (arr[i] < min_value)
min_value = arr[i];//獲取輸入資料的最小值
}
//桶的初始化
int len = (max_value-min_value)/BUCKET_SIZE+1;
vector<int> bucket[len];
//將資料分配到桶
for(int i=0;i<n;i++){
bucket[(arr[i]-min_value)/BUCKET_SIZE].push_back(arr[i]);
}
for(int i=0,j=0;i<len;i++){
//這里建議使用插入排序或者計數排序，當然也可以使用堆排序，快速排序等等
insert_sort(bucket[i]);
for(auto x:bucket[i]){
arr[j++]=x;
}
}
}
int main(){
int n;
cout << "請輸入陣列中元素的個數：";
cin >> n;
cout << "請輸入元素: " << endl;
for (int i = 0; i < n; i++)
{
cin >> arr[i];
}
cout << "排序前：" << endl;
for (int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
cout << endl;
bucket_sort(n);
cout << "排序后：" << endl;
for (int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
桶排序最好情況下使用線性時間O(n)，桶排序的時間復雜度，取決與對各個桶之間資料進行排序的時間復雜度，因為其它部分的時間復雜度都為O(n)，很顯然，桶劃分的越小，各個桶之間的資料越少，排序所用的時間也會越少，是一個用空間換時間的演算法
基數排序
基數排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次類推，直到最高位，有時候有些屬性是有優先級順序的，先按低優先級排序，再按高優先級排序，最后的次序就是高優先級高的在前，高優先級相同的低優先級高的在前，
- 取得陣列中的最大數，并取得位數；
- arr為原始陣列，從最低位開始取每個位組成r陣列；
- 對r進行計數排序（利用計數排序適用于小范圍數的特點）；
#include <iostream>
#include <queue>
using namespace std;
using namespace std;
const int MAXN = 1000;
int arr[MAXN];
queue<int> q[10];
void radix_sort(int n)
{
//獲取最大值的位數
int max_value = 0;
for (int i = 0; i < n; i++)
{
if (max_value < arr[i])
max_value = arr[i];
}
int max_digit = 0;
while (max_value)
{
max_digit++;
max_value /= 10;
}
//開始排序
int mod = 10, dev = 1;
for (int i = 0; i < max_digit; i++, mod *= 10, dev *= 10)
{
for (int j = 0; j < n; j++)
{
int ix = arr[j] % mod / dev;
q[ix].push(arr[j]);
}
int pos = 0;
for (int j = 0; j < 10; j++)
{
while (!q[j].empty())
{
arr[pos++] = q[j].front();
q[j].pop();
}
}
}
}
int main()
{
int n;
cout << "請輸入陣列中元素的個數：";
cin >> n;
cout << "請輸入元素: " << endl;
for (int i = 0; i < n; i++)
{
cin >> arr[i];
}
cout << "排序前：" << endl;
for (int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
cout << endl;
radix_sort(n);
cout << "排序后：" << endl;
for (int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
基數排序基于分別排序，分別收集，所以是穩定的，但基數排序的性能比桶排序要略差，每一次關鍵字的桶分配都需要O(n)的時間復雜度，而且分配之后得到新的關鍵字序列又需要O(n)的時間復雜度，假如待排資料可以分為d個關鍵字，則基數排序的時間復雜度將是O(d*2n) ，當然d要遠遠小于n，因此基本上還是線性級別的，基數排序的空間復雜度為O(n+k)，其中k為桶的數量，一般來說n>>k，因此額外空間需要大概n個左右，
最后
又到了碼神抒情階段了，首先就是原創不易，三連支持，還有就是劍指offer到手了，我花一個周自己先看，如果不錯，再給大家寫，希望我和大家將來都會越來越好，變禿的程序一定要變強啊 ??
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/298111.html
標籤：其他