0、簡介
1、算法詳解
1.1、冒泡排序
1.1.1、原理
冒泡排序是計算機中比較簡單的一種排序方法,他是一種穩定的排序方法.
原理是臨近的數字兩兩進行比較,按照從小到大或者從大到小的順序進行交換,
這樣一趟過去後,最大或最小的數字被交換到了最後一位,然後再從頭開始進行兩兩比較交換,直到倒數第二位時結束
1.1.2、算法實作
1 void bubble_sort(int arr[], int count)
2 {
3 int i, j, tmp;
4
5 for (i = 0; i < count-1; i++)
6 {
7 for (j = i+1; j < count; j++)
8 {
9 if (arr[i] > arr[j])
10 {
11 tmp = arr[i];
12 arr[i] =arr[j];
13 arr[j] = tmp;
14 }
15 }
16 }
17 } 冒泡排序法C語言實作
1.1.3、時間空間複雜度
空間複雜度:O(1)
時間複雜度:O(n2)
1.1.4、總結
1.1、簡單選擇排序(simple selection sort)
簡單排序跟冒泡排序的思想是一緻的,不同的是簡單排序是記錄最小(大)值的位置,最後才交換一次,比冒泡排序少了許多次交換
1.1.2、算法實作
1 void simple_selection_sort(int arr[], int count)
2 {
3 int i, j, k, tmp;
4
5 for (i = 0; i < count-1; i++)
6 {
7 k = i;
8
9 for (j = i+1; j < count; j++)
10 {
11 if (arr[k] > arr[j])
12 {
13 k = j;
14 }
15 }
16 if (k != i)
17 {
18 tmp = arr[i];
19 arr[i] = arr[k];
20 arr[k] = tmp;
21 }
22 }
23 } 簡單選擇排序的C語言實作
雖然冒泡排序的時間複雜度也是O(n2), 但是簡單選擇排序的性能還是比冒泡更好一些.
1.2、直接插入排序
1.2.1、原理
把N個待排序的元素看成為一個有序表和一個無序表，開始時有序表中隻包含一個元素(a[0])，無序表中包含有(N-1)個元素(a[1]~a[N-1]).
排序過程中每次從無序表中取出第一個元素(a[i] (i >=1))，将它插入到有序表(a[0] ~ a[i - 1])中的适當位置，使之成為新的有序表，重複N-1次可完成排序過程。
具體的插入方法是:先把a[i]指派給變量t,然後将t依次與a[i-1],a[i-2],...進行比較,将比t大的元素右移一個位置,直到發現某個j(0<=j<=i-1),使得a[j]<=t或j為(-1),把t指派給a[j+1].
1.2.2、算法實作
1 void straight_insertion_sort(int arr[], int count)
2 {
3 int i, j, tmp;
4
5 for (i = 1; i < count; i++) /* N-1次操作 */
6 {
7 tmp = arr[i]; /* 哨兵 */
8 j = i - 1;
9 while (j >= 0 && tmp < arr[j])
10 {
11 arr[j+1] = arr[j]; /* 右移 */
12 j--;
13 }
14 arr[j+1] = tmp; /* 插入 */
15 }
16 } 直接插入排序算法的C語言實作
1.2.3、時間空間複雜度
時間複雜度:O(n2)
1.2.4、總結
雖然冒泡排序與簡單選擇排序的時間複雜度都是O(n2), 但是直接插入排序的性能還是比這2個更好一些.
1.1、希爾排序(shell sort)
希爾排序又稱為“縮小增量排序”。其基本思想是：先将整個待排元素序列分割成若幹個子序列（由相隔某個“增量”的元素組成的）分别進行直接插入排序，
然後依次縮減增量再進行排序，待整個序列中的元素基本有序（增量足夠小）時，再對全體元素進行一次直接插入排序。
因為直接插入排序在元素基本有序的情況下（接近最好情況），效率是很高的，是以希爾排序在時間效率上比直接插入排序有較大提高。
1.1、直接插入排序
1.1、快速排序(quick sort)
快速排序是對冒泡排序的一種改進,是一種不穩定的排序。其基本思想是：標明一個鍵值,通常是第一個元素,然後通過一趟排序将要排序的資料分割成獨立的兩部分，
其中一部分的所有資料都小于鍵值,另外一部分的所有資料都大于等于鍵值，然後再按此方法對這兩部分資料分别進行快速排序，
整個排序過程可以遞歸進行，以此達到整個資料變成有序序列。
1 /* left,right 為數組的下标 */
2 void quick_sort(int *a, int left, int right)
3 {
4 int i = left;
5 int j = right;
6 int key = a[left];
7
8 if (left >= right)
9 {/* 如果左邊的數組大于或者等于就代表已經成分組 */
10 return;
11 }
12
13 while (i < j) /* i=j表示left到right元素已經完成分組 */
14 {
15 /* 向前尋找 */
16 while (i < j && key <= a[j])
17 /* 尋找結束的條件是:1.找到一個小餘或者大于key的數（大小取決于你想升
18 序還是降序）2.沒有符合的則i與j相遇 */
19 {
20 j--;
21 }
22 a[i] = a[j]; /* 找到一個這樣的數後就把它賦給前面的被拿走的i的值 */
23
24
25 /* 向後尋找 */
26 while (i < j && key >= a[i])
27 {
28 i++;
29 }
30 a[j] = a[i];
31 }
32 /* 此時 i = j */
33
34 a[i] = key;/* 當在當組内找完一遍以後就把中間數key回歸 */
35 quick_sort(a, left, i - 1);/* 最後用同樣的方式對分出來的左邊的小組進行同上的做法 */
36 quick_sort(a, i + 1, right);/* 用同樣的方式對分出來的右邊的小組進行同上的做法 */
37 /*當然最後可能會出現很多分左右，直到每一組的i = j 為止*/
38 } 快速排序C語言實作
空間複雜度:O(log2n)
時間複雜度:O(log2n)
1.1.4 多線程版本
http://zhidao.baidu.com/link?url=O0HAuEP_uZVxutzkjTl8ugjbD3JYC4ANADWg43iwJOYlSYLfIya9RrNr6K06TN1xfJr6w3tjVoFkpc4shYvHWq
1.1.5、總結
視訊教程:http://www.iqiyi.com/v_19rrhzyeqs.html