排序演算法小匯總
1、交換排序類
??1.1、冒泡排序
??1.2、快速排序
2、選擇排序類
??2.1、簡單選擇排序
??2.2、堆排序
3、插入排序類
??3.1、直接插入排序
??3.2、希爾排序
4、歸并排序
5、基數排序
交換排序類
冒泡排序（優化）
??冒泡排序一般將前面作為有序區（初始無元素），后面作為無序區（初始元素都在無序區里），在遍歷程序中把當前無序區最小的數像泡泡一樣，讓其往上飄，然后在無序區繼續執行此操作，直到無序區不再有元素，
??這塊是對老式冒泡排序的一種優化，因為當某次冒泡結束后，可能陣列已經變得有序，繼續進行冒泡排序會增加很多無用的比較次數，提高時間復雜度，
??所以我們增加了一個標識變數flag，將其初始化為1，外層回圈還是和老式的一樣從0到末尾，記憶體回圈我們改為從最后面向前面i（外層回圈所處的位置）處遍歷找最小的，如果在記憶體沒有出現交換，說明無序區的元素已經變得有序，所以不需要交換，即整個陣列已經變得有序，(感謝@站在遠處看童年在評論區的指正)
#include<iostream>
using namespace std;
void sort(int k[] ,int n)
{
int flag = 1;
int temp;
for(int i = 0; i < n-1 && flag; i++)
{
flag = 0;
for(int j = n-1; j > i; j--)
{
/*下面這里和i沒關系，注意看這塊，從下往上travel，兩兩比較，如果不合適就調換，
如果上來后一次都沒調換，說明下面已經按順序拍好了，上面也是按順序排好的，所以完美！
*/
if(k[j-1] > k[j])
{
temp = k[j-1];
k[j-1] = k[j];
k[j] = temp;
flag = 1;
}
}
}
}
int main()
{
int k[3] = {0,9,6};
sort(k,3);
for(int i =0; i < 3; i++)
printf("%d ",k[i]);
}
快速排序
快速排序（Quicksort），基于分治演算法思想，是對冒泡排序的一種改進，快速排序由C. A. R. Hoare在1960年提出，它的基本思想是：通過一趟排序將要排序的資料分割成獨立的兩部分，其中一部分的所有資料都比另外一部分的所有資料都要小，然后再按此方法對這兩部分資料分別進行快速排序，整個排序程序可以遞回進行，以此達到整個資料變成有序序列，
通俗來說，就是不斷的挖坑和填坑
- 1、其實就是先選擇一個基準數,然后這個基準數我們保存為x，那它所在的位置就是一個空出來的坑，
- 2、我們從右向左迭代，如果遇到比基準數小的數，就將其填到上次挖的坑中，然后它自己在的這個地方就變成了一個新的坑，
- 3、然后再從左向右迭代，找比基準數大的數，將其填到上次挖的坑中，然后它所在的地方就變成了新的坑，
- 4、最后要將基準數填入最后的坑中，然后將基準數所在的位置回傳，方便下次呼叫時候使用
//挖坑填數
int adjustArray(int s[],int l, int r) //傳入陣列和左右的下標
{
int i = l,j = r; //分別表示左半邊的下標和右半邊的下標
int x = s[l]; //默認最左邊的數就是挖的第一個坑
while(i < j) //要保證陣列中元素最少有兩個
{
//從右向左迭代，找比基準數小的
while(s[j] >= x && i < j)
j--;
if(i < j) //找到了比基準數小的
{
s[i] = s[j]; //將其填到原來挖的坑的地方上，現在j處又形成了一個新的坑
i++; //i處填入了新的數，所以i++，然后從左往右去找，在左半邊比基準數大的數
}
//從左向右迭代去找比基準數大的
while(s[i] < x && i < j)
i++;
if(i < j)
{
s[j] = s[i];
j--;
}
}
//退出時，要把坑用基準數填回去
s[i] = x;
return i; //回傳呼整后基準數的位置，方便下一次遞回呼叫的時候
}
就這樣將原來的陣列以回傳的基準數所在的位置為中心，分成了兩個陣列（理論上兩個，但在記憶體中還是在一起挨著的），然后分別對新的兩個陣列遞回進行挖坑和填坑的操作，當先前指示陣列左右兩邊的下標的變數左邊的大于或等于（一般都是等于）右邊的時候（即陣列已經被分的不能被分了），這時候原陣列就變成有序的了，因為按照上面的思路，所有左邊的都小于右邊的，那既然陣列都被分的變成一個數一個小陣列那就是左邊的數比右邊的數小，即有序，排序完成！
void quick_sort(int s[], int l, int r)
{
if(l < r)
{
int i = adjustArray(s,l,r);
//不能將上次的基準數拉入新的兩個陣列中的任何一個，因為其所在的位置已經是最終對的位置了，它左邊的數都比它小，右邊的都比它大
quick_sort(s,l,i-1);
quick_sort(s,i+1,r);
}
}
選擇排序類
簡單選擇排序
選擇排序就是每次在無序區回圈找出一個極值，將其放入指定位置（即進入有序區）來使陣列有序，一般來說是讓陣列的左邊作為有序區，右邊是無序區，
- 先從第一個元素到最后一個元素遍歷，找出最小的元素，將其和第一個元素互換位置，
- 再從第二個元素到最后一個元素遍歷，找出最小的，和第二個互換位置，
- 如此回圈，右邊無序區只剩一個元素，則排序完成！
#include<iostream>
using namespace std;
void sort(int k[],int n)
{
int min,temp; //min用來保存最小的元素的下標
for(int i = 0;i < n-1; i++)
{
min = i;
for(int j = i+1; j < n; j++) //找出無序區中的最小的元素
{
if(k[j] < k[min])
min = j;
}
if(min != i) //如果最小的元素，不是初始的，即有比它更小的就交換位置
{
temp = k[min];
k[min] = k[i];
k[i] = temp;
}
}
}
int main()
{
int k[10] = {2,5,4,6,3,8,9,7,1,0};
sort(k,10);
for(int i = 0;i < 10;i++)
cout<<k[i]<<" ";
}
堆排序
堆排序采用大頂堆或著小頂堆，我們這里采用大頂堆來排序，
用一棵完全二叉樹來模擬一個大頂堆，大頂堆的規則如下：每個結點的值都大于它的孩子結點的值，如下圖：
??這樣，如果我們每次將大頂堆的根節點依次和陣列的最后一個，倒數第二個，倒數第三個......做交換，每次交換完后，需要從根節點到與之交換的那個結點之前的結點之間進行調整大頂堆，保證大頂堆的符合上述規則，
??在完全二叉樹中，如果用順序結構來存盤這棵樹，那么某個結點和它左右孩子結點之間存在以下關系（層序遍歷）：左孩子下標等于雙親結點下標的2倍，右孩子下標等于雙親結點2倍+1，
交換函式
void swap(int k[], int i, int j)
{
int temp = k[i];
k[i] = k[j];
k[j] = temp;
}
調整大頂堆的函式
void HeapAdjust(int k[], int s, int n) //從s到n開始調整大頂堆,s表示待調整的結點
{
int temp = k[s]; //保存當前需要調整的結點
for(int i = 2*s; i <= n; i*=2) //2*s表示s這個結點的左孩子，i*=2表示當前結點的左孩子結點，也就是下一個檢查的結點，因為移動當前檢查的結點后，可能會對其孩子結點的規則完整性破壞，所以需要往下檢查
{
if(i < n && k[i] < k[i+1]) //k[i]表示左孩子，k[i+1]表示右孩子,i<n是為了保證不是最后一個結點
{
i++; //永遠讓i指向較大的孩子結點
}
if(temp >= k[i]) //如果待調整的雙親大于兩孩子中較大的孩子,則不需要調整
{
break;
}
//下面將較大的更新為雙親結點
k[s] = k[i];
s=i;
}
k[s] = temp;
}
/**
對上面for回圈做一個解釋，當檢查到較上的結點時候，移動后不能保證樹的規則，
應該繼續檢查其孩子結點，因為做了交換后可能會破壞孩子結點的大頂堆規則
*/
對堆排序的實作
為了方便起見，陣列不用第0號元素，從第一號元素開始，
假設一共n個結點，第n/2個結點剛好是最后一個擁有孩子結點的結點，這個也是完全二叉樹的規律，而初始我們就應該從下往上去檢查，因為上面的結點是根據下面的結點檢查的，
#include <iostream>
using namespace std;
void HeapSort(int k[], int n)
{
for(int i = n/2; i > 0; i--)//第n/2個結點剛好是最后一個擁有孩子結點的結點，這個也是完全二叉樹的規律
{
HeapAdjust(k,i,n);
}
for(int i = 1; i < 10; i++) //此處是為了除錯，查看交換前第一次構造的大頂堆
cout<<k[i]<<" ";
for(int i = n; i > 1; i--)
{
swap(k,1,i);
HeapAdjust(k,1,i-1);
}
}
int main()
{
int k[10] = {-1,3,2,7,5,8,9,0,1,6};
HeapSort(k,9);
system("pause"); //此處是為了做一下除錯，查看交換前構造的第一個大頂堆
for(int i = 1; i < 10; i++)
cout<<k[i]<<" ";
}
插入排序類
直接插入排序
??（從小到大排列）直接插入排序就是：遍歷這個陣列，然后如果發現后一個比前一個小，則將后一個較小的拿出來，記為x，然后與前面的依次作比較，如果比x大，則將其向后退一個位置，直到碰到一個比x小的元素，則將x放到它的后面即可，這樣等到遍歷完這個陣列后，它就會變成有序的，
??下面是一次外層回圈的演示，對整個陣列遍歷一遍，作如下操作則可
#include<iostream>
using namespace std;
void Insert_Sort(int k[],int n)
{
int temp,j,i;
for(i = 1; i < n; i++)
{
if(k[i] < k[i-1])
{
temp = k[i];
for( j = i-1; k[j] > temp && j >= 0; j--)
k[j+1] = k[j];
k[j+1] = temp;
}
}
}
int main()
{
int k[10] = {3,5,1,7,2,0,8,9,4,6};
Insert_Sort(k,10);
for(int i = 0; i < 10; i++)
cout<<k[i]<<endl;
return 0;
}
希爾排序
??希爾排序是對插入排序的一種改進，先取一個小于n的整數d1作為第一個增量，把檔案的全部記錄分組，所有距離為d1的倍數的記錄放在同一個組中，先在各組內進行直接插入排序；然后，取第二個增量d2 < d1重復上述的分組和排序，直至所取的增量 =1( < …< d2< d1)，即所有記錄放在同一組中進行直接插入排序為止，
#include<iostream>
using namespace std;
void Insert_Sort(int k[],int n)
{
int temp,j,i;
int gap = n;
do
{
gap = gap/3 + 1;
for(i = gap; i < n; i++)
{
if(k[i] < k[i-gap])
{
temp = k[i];
for( j = i-gap; k[j] > temp && j >= 0; j-=gap)
{
k[j+gap] = k[j];
}
k[j+gap] = temp;
}
}
}while(gap > 1);
}
int main()
{
int k[10] = {3,5,1,7,2,0,8,9,4,6};
Insert_Sort(k,10);
for(int i = 0; i < 10; i++)
cout<<k[i]<<" ";
return 0;
}
歸并排序
歸并排序，基于分治演算法思想，就比如是比武大賽一樣，先對資料進行分組，兩兩進行比較，并排序，然后將有序的兩個小陣列進行歸并，得到一個新陣列，再和其他新得到的陣列進行兩兩歸并，如此重復，直到歸并為一個大陣列，此時，此陣列有序！
#include <iostream>
using namespace std;
void Merge(int array[], int start, int mid, int end)
{
//start到mid表示第一個陣列，mid+1到end表示第二個陣列
int newarray[end - start + 1];
//對兩個陣列進行歸并
int p = start, q = mid + 1, r = 0; //分別指示第一個陣列，第二個陣列，和第三個新陣列
while(p <= mid && q <= end)
{
if(array[p] <= array[q])
{
newarray[r++] = array[p++];
}
else
{
newarray[r++] = array[q++];
}
}
//左側小集合還有剩余，依次歸并到大集合尾部
while(p <= mid)
{
newarray[r++] = array[p++];
}
//右側小集合還有剩余，依次歸并到大集合尾部
while(q <= end)
{
newarray[r++] = array[q++];
}
//將大集合元素依次復制回原陣列
for(int i = 0; i < end - start + 1; i++) //to do
array[i+start] = newarray[i];
}
void Merge_Sort(int array[], int start, int end)
{
int mid = (start + end) / 2;
if(start < end)
{
Merge_Sort(array,start,mid);
Merge_Sort(array,mid+1,end);
//合并
Merge(array,start,mid,end);
}
}
int main()
{
int k[10] = {3,9,6,1,8,4,0,7,2,5};
Merge_Sort(k,0,9);
for (int i = 0; i < 10; ++i)
{
cout<<k[i]<<" ";
}
}
基數排序
個人理解(最好先了解一下桶排序)：
??從待排序陣列每個數字的基數開始排序，然后一直到最大數的最高位，準備10個桶，從低位開始分別將其放入對應編號為0-9的桶中，等到低位排完得到一個子序列，再將這個序列按照次低位的大小進入相應的桶中，一直排到最高位為止，陣列排序完成，
演算法步驟
- 先找出所有數中的最高位數，即回圈次數，要存入桶和出桶這么多次
- 每次回圈用一個count[10]陣列記錄每個桶中的數字個數（回圈開始之前，要記得將上次回圈時count中保存的值初始化為0）
- 遍歷陣列中每一個數，將其放入指定的桶中
- 按0-9的順序又將桶中元素存回陣列，覆寫之前的值
先對個位排序
再對十位排序
繼續百位
一直到最高位
此時將桶中數字依次輸出，即有序！
#include <iostream>
#include <cmath>
using namespace std;
//求資料的最大位數，可以作為對內私有的函式，先找陣列中的最大數，然后求最大數的位數
int maxbit(int data[], int n)
{
int max = 0, bit = 0;
for (int i = 0; i < n; i++)
if (data[i] > max)
max = data[i];
while (max != 0)
{
max /= 10;
bit++;
}
return bit;
}
void sort(int data[], int n)
{
int bit = maxbit(data, n);
int count[10]; //統計每個桶中數的個數
int* bucket = new int[10 * n]; //二維陣列，10個桶，每個桶容量最大是n，即所有元素存到一個桶中
for (int i = 1; i <= bit; i++) //回圈最高位數次
{
int x = 0;
for (int p = 0; p < 10; ++p) //每次將統計桶中個數的陣列清零
count[p] = 0;
for (int j = 0; j < n; j++) //遍歷陣列中每一個數，將其放入指定的桶中
{
int b = data[j];
//取一個數的倒數第n位的數字，就是讓它除以10的n-1次方，再取10的余數
b /= pow(10, i - 1);
b %= 10;
count[b]++;
bucket[b * n + count[b]] = data[j]; //放入桶中
}
//將桶中的資料按順序存回陣列中
for (int r = 0; r < 10; r++)
{
for (int t = 1; t <= count[r]; t++)
{
data[x] = bucket[r * n + t];
x++;
}
}
}
}
int main()
{
int data[10] = { 34, 90, 12, 21, 128, 231412, 678, 123, 3, 10 };
sort(data, 10);
for (int i = 0; i < 10; ++i)
{
cout << data[i] << " ";
}
system("pause");
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/137715.html
標籤：其他