1 快速排序

文章原地址：https://blog.csdn.net/morewindows/article/details/6684558
快速排序的平均時間復雜度是0(NlogN)，它采用了一種分治的策略，通常稱其為分治法。該方法的基本思想是：

1. 先從數列中取出一個數作為基準數。
2. 分區：將大于等于這個數放到它的右邊，小于它的數全放在它的左邊
3. 再對左右區間進行快排

雖然快速排序稱為分治法，但分治法這三個字顯然無法很好概括快速排序的全部步驟，因此我對快速排序做了進一步的說明：挖坑填數+分治法。

以一個數組作為示例，取區間第一個數為基準數。

初始時，i = 0; j = 9; X = a[i] = 72

由于已經將a[0]中的數保存到X中，可以理解成在數組a[0]上挖了個坑，可以將其它數據填充到這來。

從j開始向前找一個比X小或等于X的數。當j=8，符合條件，將a[8]挖出再填到上一個坑a[0]中。a[0]=a[8]; i++; 這樣一個坑a[0]就被搞定了，但又形成了一個新坑a[8]，這怎么辦了？簡單，再找數字來填a[8]這個坑。這次從i開始向后找一個大于X的數，當i=3，符合條件，將a[3]挖出再填到上一個坑中a[8]=a[3]; j–;

數組變為：

i = 3; j = 7; X=72

再重復上面的步驟，先從后向前找，再從前向后找。

從j開始向前找，當j=5，符合條件，將a[5]挖出填到上一個坑中，a[3] = a[5]; i++;

從i開始向后找，當i=5時，由于i==j退出。

此時，i = j = 5，而a[5]剛好又是上次挖的坑，因此將X填入a[5]。依次類推。

代碼實現

void quick_sort(int *arr,int l,int r)
{if(l<r){   int i=l,j=r,x=arr[i];while(i<j){/* 從右往左找小于x的值，找到之后，放到arr[i++] */while(i<j && arr[j]>=x){j--;}if(i<j){arr[i++]=arr[j];}/* 從左往右找大于等于x的值，找到之后，放到arr[j--] */while(i<j && arr[i]<x){i++;}if(i<j){arr[j--]=arr[i];}}/* 放x */arr[i]=x;/* 對x左右兩個區間進行快排 */quick_sort(arr,l,i-1);quick_sort(arr,i+1,r);}
}

測試：

int main(void)
{int arr[]={72,6,57,88,60,42,83,73,48,85};quick_sort(arr,0,9);for(int i=0;i<10;i++){printf("%d ",arr[i]);}return 0;
}

stdlib庫快排

stdlib庫提供了快排函數qsort

void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*))

• base是要排序的的數組
• nitems是數組中元素個數
• size是每個元素所占字節數
• compar是比較函數

#include <stdio.h>
#include <stdlib.h>int cmp(void *a,void *b)
{return *(int *)a - *(int *)b;
}int main(void)
{int arr[]={72,6,57,88,60,42,83,73,48,85};qsort(arr,10,sizeof(int),cmp);for(int i=0;i<10;i++){printf("%d ",arr[i]);}return 0;
}

2 堆排序

文章原地址：https://www.cnblogs.com/lanhaicode/p/10546257.html
堆是一個完全二叉樹，通俗的說，堆就是利用完全二叉樹的結構來維護的一維數組。
按照堆的特點可以把堆分為大頂堆和小頂堆：

• 大頂堆：每個結點的值都大于等于其左右孩子的值
• 小頂堆：每個結點都小于等于其左右孩子的值。

在用一維數組描述的堆中，如果父結點的下標是i，則左孩子的結點的下標是2i+1，右孩子是2i+2；所以如果孩子結點的下標是i，則父結點的下標結點j是：

j = (i-1)/2	/* 整數相除，取整，相當于向下取整數 */

我們用簡單的公式來描述一下堆的定義：

• 大頂堆：arr[i] >= arr[2*i+1] && arr[i] >= arr[2*i+2]
• 小頂堆：arr[i] <=arr[2*i+1] && arr[i] <= arr[2*i+2]

下面以大頂堆為例。

堆排序的基本思想

將待排序序列構造成一個大頂堆，此時，整個序列的最大值就是堆頂的根結點，然后把根結點和最后一個結點（數組最后一個元素）交換位置，那么末尾元素此時就是最大元素了。

1. 先把n個元素的無序序列，構建成大頂堆
2. 將根結點與最后一個元素交換位置。（將最大元素放到數組末端）
3. 交換過后可能不再滿足大頂堆的條件，所以需要將剩下的n-1個元素重新構建成大頂堆
4. 重復第二步和第三步直到整個數組排序完成。

如何構造一個大頂堆

建立一個大頂堆是從最后一個非葉子結點開始從下往上調整的，也就是從最后一個結點的父結點開始。

這里以int a[6] = {7, 3, 8, 5, 1, 2}為例子。數組的長度是6，則最后一個結點的下標是5.

先要找到最后一個結點的父結點：(5-1)/2=2。2所對應的數是8。然后比較該結點值和它的左右孩子結點的值，如果小于其左右孩子的值，就交換，把最大左右孩子最大的值放到該結點
8只有一個左子樹，左子樹的值為2，不需要跳轉

下一步，繼續找到下一個非葉子結點（其實就是當前坐標-1就行了），該結點的值是3，小于其左子樹的值，交換值。


下一步，繼續找下一個非葉子結點，該結點的值是7，小于右子樹，需要交換


下一步，檢查調整后的子樹，是否滿足大頂堆的性質，如果不滿足則繼續調整（這里因為只將右子樹的值與根節點互換，只需要檢查右子樹是否滿足，而7>2剛好滿足大頂堆的性質，就不需要調整了）

到這里大頂堆的構造就完成了。

排序

大頂堆已經構造好了，下一步交換根結點和最后一個結點（將最大值放到數組末端），此時最大的元素就歸位了，然后對剩下的5個元素重復上面的步驟：

剩下只有5個元素，把剩下的結點變為大頂堆

將根結點（7）與最后一個結點交換：

依次類推，最后得到排好序的數組：

/* Function: 構建大頂堆 */
void BuildMaxHeap(int *heap, int len)
{int i;int temp;for (i = len/2-1; i >= 0; i--){if ((2*i+1) < len && heap[i] < heap[2*i+1])    /* 根節點小于左子樹 */{temp = heap[i];heap[i] = heap[2*i+1];heap[2*i+1] = temp;/* 檢查交換后的左子樹是否滿足大頂堆性質 如果不滿足 則重新調整子樹結構 */if ((2*(2*i+1)+1 < len && heap[2*i+1] < heap[2*(2*i+1)+1]) || (2*(2*i+1)+2 < len && heap[2*i+1] < heap[2*(2*i+1)+2])){BuildMaxHeap(heap, len);}}if ((2*i+2) < len && heap[i] < heap[2*i+2])    /* 根節點小于右子樹 */{temp = heap[i];heap[i] = heap[2*i+2];heap[2*i+2] = temp;/* 檢查交換后的右子樹是否滿足大頂堆性質 如果不滿足 則重新調整子樹結構 */if ((2*(2*i+2)+1 < len && heap[2*i+2] < heap[2*(2*i+2)+1]) || (2*(2*i+2)+2 < len && heap[2*i+2] < heap[2*(2*i+2)+2])){BuildMaxHeap(heap, len);}}}
}/* Function: 交換交換根節點和數組末尾元素的值*/
void Swap(int *heap, int len)
{int temp;temp = heap[0];heap[0] = heap[len-1];heap[len-1] = temp;
}int main()
{int a[6] = {7, 3, 8, 5, 1, 2};int len = 6;    /* 數組長度 */int i;for (i = len; i > 0; i--){BuildMaxHeap(a, i);Swap(a, i);}for (i = 0; i < len; i++){printf("%d ", a[i]);}return 0;
}

3 冒泡排序

https://www.runoob.com/w3cnote/bubble-sort.html