經典排序演算法
預定義
#define Ty int // 以整型為例
交換資料的函式
void swap(Ty* elems,int i,int j) {
Ty temp=elems[i];
elems[i]=elems[j];
elems[j]=temp;
}
// 如果確認只用整型資料使用下面的代碼會更快，因為減少了函式壓堆疊，也使用了位運算
#define SWAP_INT(a, b) \
{ \
a = (a) ^ (b); \
b = (a) ^ (b); \
a = (a) ^ (b); \
}
冒泡排序
原理：將一段序列的最大值（最小值）拿到最左邊或者最右邊的操作，使用回圈重復操作，（每輪排序都會少一個最大值或最小值），當最后只剩下一個資料的時候整個序列就已經排好序了，
冒泡排序的原理很簡單，使用代碼實作也很簡單，也是所有排序演算法里面最簡單的一個，
具體代碼實作：
void bubSort(Ty* elems,int size) {
for (int i = 0;i < size;size--) { //輪
for (int j = i + 1;j < size;j++) { //找剩余元素中的最值
if (elems[j] < elems[j-1]) {
swap(elems,j,j-1);
}
}
}
}
void bubSort(Ty* elems,int size) {
for(int i=0;i<size-1;i++)
for(int j=i+1;j<size;j++)
if(elems[i]<elems[j])
swap(elems,i,j);
}
直接使用兩層回圈去實作，外層回圈主要作用是存放最大值或最小值的，記憶體回圈的主要作用是找到發生沖突的元素，如果發生沖突就交換兩個資料，當兩層回圈的結束的時候整個序列就自然排好序了，時間復雜度為O(n^2).
選擇排序
原理：基本思想和冒泡排序是一樣的，選擇排序相對于冒泡排序的優點就是減少交換次數，演算法思想都是在序列中找到最大值（最小值），然后存放好下次進入回圈就訪問不到這個最大值（最小值），當兩層回圈都結束的時候序列就自然排好了，
具體代碼實作：
void selectSort(Ty* elems,int size) {
for(int i=0;i<size-1;i++) {
int minPos=i;
for(int j=i+1;j<size;j++)
if(elems[minPos]>elems[j])
minpos=j;
swap(elems,i,minPos);
}
}
插入排序
原理：基本思想還是冒泡排序，不過插入排序是兩邊相靠的冒泡，所以在序列部分有序的情況下，插入排序的效率要比冒泡排序效率高，從序列的尾部開始往前比較，如果當前的資料小于（大于）前一個的資料就進行交換，否則進入下一次回圈，直到外層回圈遍歷完整個序列就自然排好序了，
具體代碼實作：
//使用交換函式
void insertSort(Ty* elems,int size) {
for(int i = 1;i < size;i++)
for(int j = i;j > 0 && elems[j-1] > elems[j];j--)
swap(elems,j-1,j);
}
//不使用交換函式
void insertSort(Ty* elems,int size) {
for (int i = 1;i < size;i++) {
int j = i;
int temp = arr[j];
for (;j >= 1 && temp < arr[j-1];j--)
arr[j] = arr[j-1];
arr[j] = temp;
}
}
希爾排序
原理：希爾排序是建立在插入排序的基礎上進行優化的排序演算法，所以希爾排序又叫做優化版的插入排序，
代碼實作：
- 將間隔定為4
void shellSort(Ty* elems,int size) {
for(int h = 4;h >= 1;h = h >> 1)
for(int i = h;i < size;i++)
for(int j = i;j >= h && elems[j] > elems[j-h];j -= h)
swap(elems,j,j-h);
}
- 使用常用的序列號
//使用交換函式
void shellSort(Ty* elems,int size) {
int h = 1;
while(h < size/3) h = 3*h + 1;
while(h >= 1) {
for(int i = h;i < size;i++)
for(int j = i;j >= h && elems[j] > elems[j-h];j -= h)
swap(elems,j,j-h);
h /= 3;
}
}
//不使用交換函式
void shellSort(Ty* elems,int size) {
int h = 1;
int t = length/3;
while (h < t) h = 3*h + 1;
while (h >= 1) {
for (int i = h;i < length;i++) {
int j = h;
Ty temp = arr[j];
for (;j >= h && temp < arr[j-h];j-=h)
arr[j] = arr[j-h];
arr[j] = temp;
}
h /= 3;
}
}
# 實體解釋
size=13,h=4 # h=13/3
h
|
4 6 8 7 9 5 3 1 2 10 0 11 12
||
ij
# 4<9 so i++;j=i
h
|
4 6 8 7 9 5 3 1 2 10 0 11 12
||
ij
# 6>5 交換 j-=h
h
|
4 5 8 7 9 6 3 1 2 10 0 11 12
| |
j i
# j<h i++;j=i
# 依此類推
快速排序
原理：快速排序的核心思想是設立一個軸，然后其他資料都和這個軸作比較，最后把軸放在序列的中間，執行完一遍快速排序后左邊的資料都比軸小，右邊的資料都比軸大，然后遞回下去，當遞回結束的時候就拍好序了，快速排序的排序很快，但是當資料形成一邊倒的情況的時候就發揮不出快速排序的優勢，
具體代碼實作：
//稍微修改一下適用于單鏈表的快速排序
void quickSort(Ty *elems, int first, int last) {
if (first >= last || first < 0 || last < 0)
return;
Ty privot = elems[first];
int i = first + 1;
int j = first + 1;
while (j <= last) {
if (elems[j] < privot) {
swap(&elems[i], &elems[j]);
i++;
}
j++;
}
swap(&elems[first], &elems[i - 1]);
quickSort(elems, first, i - 1);
quickSort(elems, i, last);
}
//僅僅適用于陣列的快速排序
void quickSort(Ty* elems,int left,int right) {
if (left >= right) return;
int i = left;
int j = right;
Ty privot = elems[i];
while (i < j) {
while (i < j && arr[j] >= privot) --j;
arr[i] = arr[j];
while (i < j && arr[i] <= privot) ++i;
arr[j] = arr[i];
}
arr[i] = privot;
quickSort(elems,left,i - 1);
quickSort(elems,i + 1,right);
}
歸并排序
原理：把要排序的序列拆分成多個含有一個資料的序列，然后按照從小到大（從大到小）進行合并，這樣就自然的將無序的序列排好序，
具體代碼實作：
void merge(int arr[],int left,int mid,int right,int* temp) {
int i = left;
int j = mid + 1;
int k = left;
while (i <= mid && j <= right) temp[k++] = arr[i] < arr[j] ? arr[i++] : arr[j++];
while (i <= mid) temp[k++] = arr[i++];
while (j <= right) temp[k++] = arr[j++];
for (i = left;i <= right;i++)
arr[i] = temp[i];
}
void merge_sort(int arr[],int left,int right,int* temp) {
if (left >= right) return;
int mid = left + ((right - left) >> 1);
merge_sort(arr,left,mid,temp);
merge_sort(arr,mid + 1,right,temp);
merge(arr,left,mid,right,temp);
}
void mergeSort(int arr[],int length) {
int* temp = (int*)malloc(sizeof(int)*length);
assert(temp);
merge_sort(arr,0,length - 1,temp);
free(temp);
}
堆排序
堆分有小頂堆和大頂堆，而堆排序又分有外堆和內堆，
-
外堆
意思是，而外申請一段和原來陣列一樣大的記憶體大小，并將陣列的元素構造成小頂堆或大頂堆，根據排序的順序和逆序確定要構成的堆結構是大頂堆還是小頂堆，現以最終序列是順序排序（從小到大）為例，則需要構成的堆結構是小頂堆，因為小頂堆可以快速的找到序列的最小值，如果將小頂堆的資料依次彈出，則每次彈的都是剩余序列的最小值，并且每次彈出就放到原來的陣列中，當小頂堆里的資料都彈出來完了，原來的陣列也自然有序了，如果要求最終序列是逆序的則構造的堆結構是大頂堆，然后操作是一樣的，時間復雜度是\(O(nlogn)\). 空間復雜度是\(O(n)\). -
內堆
意思是，不需要額外申請空間，直接在原來的陣列上進行操作，現以最終序列是順序排序（從小到大）為例，則需要構成的堆結構是大頂堆，在原來的陣列上構造堆結構稱之為 “堆化” ，heapify.形成大頂堆后，將堆頂依次彈出并立即放陣列的尾部，反復操作此步驟直到最后一個資料，最終自然形成從小到大依次排好序，
//外堆
//堆的結構體描述
typedef struct Heap {
Ty* root;
int size;
}Heap;
//創建堆記憶體
Heap* creatHeap(int capacity) {
Heap* heap = (Heap*)malloc(sizeof(Heap));
assert(heap);
heap->root = (Ty*)malloc(sizeof(Ty) * (capacity+1) );
heap->size = 1;
return heap;
}
//入堆
//先將要插入的資料插入到堆的尾部，然后向上滲透，爬到對應的位置，就把資料放進去即可
void pushHeap(Heap* heap,Ty data) {
int current = heap->size++;
int parent = current >> 1;
heap->root[current] = data;
while (parent) {
if (heap->root[current] < heap->root[parent]) {
swap(heap->root,current,parent);
current = parent;
parent >>= 1;
}
else break;
}
}
//出堆
//先將堆頂元素保存下來，然后使用堆的尾部覆寫堆頂，然后往下滲透，走到對應的位置，就把資料放進去，然后回傳保存的元素
Ty popHeap(Heap* heap) {
int current = 1;
int rchild = 3;
int n = --heap->size;
Ty ret = heap->root[1];
heap->root[1] = heap->root[n];
while (rchild < n) {
int small = heap->root[rchild - 1] < heap->root[rchild] ? rchild - 1 : rchild;
if (heap->root[small] < heap->root[current]) {
swap(heap->root,current,small);
current = small;
rchild = (current << 1) + 1;
}
else break;
}
return ret;
}
//內堆
//在原來陣列的基礎上直接操作，其實就是入堆和出隊直接結合，不需要額外申請空間
void heapify(int arr[],int current,int length) {
int rchild = (current << 1) + 2;
int large;
while (rchild <= length && (arr[large = rchild == length ? rchild-1 : (arr[rchild-1] > arr[rchild] ? rchild-1 : rchild)] > arr[current])) {
swap(arr,large,current);
current = large;
rchild = (current << 1) + 2;
}
}
void heapSort(int arr[],int length) {
int current = length >> 1;
while (current >= 0) heapify(arr,current--,length);
while (length) {
swap(arr,0,--length);
heapify(arr,0,length);
}
}
計數排序
前面的演算法都是基于比較的排序，計數排序是利用了陣列的下標天然有序原理進行排序，所以計數排序是基于統計而排序的排序演算法，演算法的核心思想是遍歷一個無序陣列，將遍歷到的資料按它的數值找到統計陣列的對應下標將其放入統計陣列中，依次類推，直到無序的陣列的每一個資料都被遍歷完之后統計陣列也已經初始化完畢，接下來就是遍歷統計陣列如果遍歷到的空間是大于零的就將其下標存入原來的陣列中，直到統計陣列被遍歷完，最終可以排好序，
void countSort(int arr[],int length,int max) {
int* count = (int*)calloc(max,sizeof(int));
for (int i = 0;i < length;i++) {
count[arr[i]]++;
}
for (int i = 0,j = 0;i < max;i++) {
while (count[i]--)
arr[j++] = i;
}
free(count);
}
基數排序
桶排序的思想，按照數字的位數進行排序，準備0-9的鏈式佇列，從低位開始到高位進行排序，當最高位被排好序后原來的序列自然排好序了，
例如：對以下序列進行基數排序
578，234，86，432，512，618，384
排序程序：
第一輪（\(在第零輪的基礎上按10^0位排\)）：432，512，234，384，86，578，618
第二輪（\(在第一輪的基礎上按10^1位排\)）：512，618，432，234，578，384，86
第三輪（\(在第二輪的基礎上按10^2位排\)）：86，234，384，432，512，578，618
第三輪結束序列自然排好序，86不夠3位數，就往前面補零，即86 = 086.
void redixSort(int arr[], int length) {
int i;
int j;
int ii;
int jj;
int temp[10][10];
for (ii = 0; ii < 10; ii++)
for (jj = 0; jj < 10; jj++)
temp[ii][jj] = -1;
for (int k = 10; k < 10000; k *= 10) {
for (i = 0; i < length; i++) {
int index = (arr[i] % k) / (k / 10);
j = 0;
while (temp[index][j] != -1)
j++;
temp[index][j] = arr[i];
}
i = 0;
for (ii = 0; ii < 10; ii++) {
for (jj = 0; jj < length && temp[ii][jj] != -1; jj++) {
arr[i++] = temp[ii][jj];
temp[ii][jj] = -1;
}
}
}
}
我在去年已經先將視頻講解發布到B站上了，但是當時沒有將檔案發布，直接放到博客里讓大家訪問和學習吧，下面是本次內容的視頻鏈接：
B站視頻鏈接：Cukor丘克
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/539711.html
標籤：其他
下一篇：地下城地圖圖塊生成演算法