各種排序算法（連載中。。。），排序算法連載中...
新博客開張，就拿排序算法開張吧。。。我盡量從最簡單的排序算法開始，不定期連載更新中~
ps:在我學會JAVA和C++之前，程序都用C來寫吧，水平有限，大家湊和著看吧 重點是算法！~
（圖片來源於網絡）
目錄：
1.插入排序——直接插入排序。
2.插入排序——希爾排序。
3.選擇排序——簡單選擇排序。
4.選擇排序——堆排序。
5.交換排序——冒泡排序。
6.交換排序——快速排序（大力推薦使用）。
7.歸並排序。
8.基數排序。
1.插入排序——直接插入排序。
具體算法描述如下：（個人認為很好理解）
ps：可以采用二分查找法來減少比較操作的數目，稱為二分查找插入排序法。
C語言代碼如下：
![]()
1 #include<stdio.h>
2 #define MAXN 10000
3 int main()
4 {
5 printf("請輸入一組數，每個數之間以“，”隔開，Enter鍵結束輸入\n");
6 int arr[MAXN]; //定義一個足夠大的數組
7 int i=0,j,k,count = 0;
8 while(count<MAXN) //讀入數組，存入數組a中；
9 {
10 scanf("%d",&arr[i++]);
11 count++;
12 if(getchar() == '\n') break;
13 }
14 int target;
15 for (i=1; i<count; i++) //開始排序
16 {
17 j=i;
18 target = arr[i]; //從第二個數開始，依次作為參考點
19 while (j>0 && target<arr[j-1])
20 {
21 arr[j] = arr[j-1];
22 j--;
23 }
24 arr[j] = target;
25 }
26 for(i=0;i<count;i++)
27 printf("%d ",arr[i]);
28 return 0;
29 }
<--點擊左側+展開
ps：修改：輸入時以一個空格隔開
2.插入排序——希爾排序（相對於直接插入排序，效率進一步提高）。
希爾排序(Shell Sort)是插入排序的一種。是針對直接插入排序算法的改進。該方法又稱縮小增量排序，因DL．Shell於1959年提出而得名。
希爾排序（漸減增量排序法）思想：1959年Donald L. Shell提出Shell排序法 ，源自對直接插入算法的改進.
具體算法描述如下：
先將整個待排元素序列分割成若干個子序列（由相隔某個“增量”的元素組成的）分別進行直接插入排序，然後依次縮減增量再進行排序，待整個序列中的元素基本有序（增量為1）時，再對全體元素進行一次直接插入排序。因為直接插入排序在元素基本有序的情況下（接近最好情況），效率是很高的，因此希爾排序在時間效率上比前兩種方法有較大提高。
C語言代碼如下：
![]()
1 #include<stdio.h>
2 #define MAXN 10000
3
4 void shellsort(int a[], int n)
5 {
6 int i, j, gap;
7 for (gap = n / 2; gap > 0; gap /= 2)
8 {
9 for (i = 0; i < gap; i++) //直接插入排序
10 {
11 for (j = i + gap; j < n; j += gap)
12 if (a[j] < a[j - gap])
13 {
14 int temp = a[j];
15 int k = j - gap;
16 while (k >= 0 && a[k] > temp)
17 {
18 a[k + gap] = a[k];
19 k -= gap;
20 }
21 a[k + gap] = temp;
22 }
23 }
24 }
25 }
26
27 int main()
28 {
29 printf("請輸入一組數，每個數之間以1個空格隔開，Enter鍵結束輸入\n");
30 int arr[MAXN]; //定義一個足夠大的數組
31 int i=0,j,k,count = 0;
32 while(count<MAXN) //讀入數組，存入數組a中；
33 {
34 scanf("%d",&arr[i++]);
35 count++;
36 if(getchar() == '\n') break;
37 }
38 shellsort(arr,count);
39 for(i=0;i<count;i++)
40 printf("%d ",arr[i]);
41 return 0;
42 }
<--點擊左側+展開
3.選擇排序——簡單選擇排序。
又到了一種簡單易理解的算法 0.0
原理如下（摘自百度百科）：
設所排序序列的記錄個數為n。i取1,2,…,n-1,從所有n-i+1個記錄（Ri,Ri+1,…,Rn）中找出排序碼最小的記錄，與第i個記錄交換。執行n-1趟 後就完成了記錄序列的排序。
C語言代碼如下：
![]()
1 #include<stdio.h>
2 #define MAXN 10000
3 int main()
4 {
5 printf("請輸入一組數，每個數之間以“，”隔開，Enter鍵結束輸入\n");
6 int arr[MAXN]; //定義一個足夠大的數組
7 int i=0,j,k,count = 0;
8 while(count<MAXN) //讀入數組，存入數組a中；
9 {
10 scanf("%d",&arr[i++]);
11 count++;
12 if(getchar() == '\n') break;
13 }
14
15 for(i=0;i<count;i++)
16 {
17 k=i;
18 for(j=i+1;j<count;j++)
19 {
20 if(a[k]>a[j])
21 k=j;
22 }
23 if (k!=i)
24 {
25 t=a[i]; //互換
26 a[i]=a[k];
27 a[k]=t;
28 }
29
30 }
31 for(i=0;i<count;i++)
32 printf("%d ",arr[i]);
33 return 0;
34 }
<--點擊左側+展開
4.選擇排序——堆排序。
待補充...
5.交換排序——冒泡排序。
這個算法的名字由來是因為越大的元素會經由交換慢慢“浮”到數列的頂端，故名。
由於冒泡排序簡潔的特點，它通常被用來對於計算機程序設計入門的學生介紹算法的概念。
冒泡排序算法的運作如下：（來自百度百科）
-
比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
-
對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。在這一點，最後的元素應該會是最大的數。
-
針對所有的元素重復以上的步驟，除了最後一個。
-
持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。
C語言代碼如下：
![]()
1 #include<stdio.h>
2 #define MAXN 10000
3
4 void bubble_sort(int a[],int n)
5 {
6 int i,j,temp;
7 for(j=0;j<n-1;j++)
8 {
9 for(i=0;i<n-1-j;i++)
10 {
11 if(a[i]>a[i+1]) //數組元素大小按升序排列
12 {
13 temp=a[i]; //交換
14 a[i]=a[i+1];
15 a[i+1]=temp;
16 }
17 }
18 }
19 }
20 int main()
21 {
22 printf("請輸入一組數，每個數之間以1個空格隔開，Enter鍵結束輸入\n");
23 int arr[MAXN]; //定義一個足夠大的數組
24 int i=0,j,k,count = 0;
25 while(count<MAXN) //讀入數組，存入數組a中；
26 {
27 scanf("%d",&arr[i++]);
28 count++;
29 if(getchar() == '\n') break;
30 }
31 bubble_sort(arr,count);
32 for(i=0;i<count;i++)
33 printf("%d ",arr[i]);
34 return 0;
35 }
<--點擊左側+展開
6.交換排序——快速排序（大力推薦使用）。
終於寫到了我最喜歡的快速排序算法。
原理介紹如下：（摘自百度百科）
快速排序（Quicksort）是對冒泡排序的一種改進。由C. A. R. Hoare在1962年提出。它的基本思想是：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。 ![]()
1 #include<stdio.h>
2 #define MAXN 10000
3
4 void QuickSort(int a[],int numsize)
5 {
6 int i=0,j=numsize-1;
7 int key=a[0];
8 if(numsize>1) //確保數組長度至少為2，否則無需排序
9 {
10 while(i<j) //循環結束條件
11 {
12 for(;j>i;j--)
13 if(a[j]<key)
14 {
15 a[i++]=a[j];
16 break;
17 }
18 for(;i<j;i++)
19 if(a[i]>key)
20 {
21 a[j--]=a[i];
22 break;
23 }
24 }
25 a[i]=key;
26 QuickSort(a,i); //遞歸
27 QuickSort(a+i+1,numsize-i-1); //遞歸
28 }
29 }
30
31 int main()
32 {
33 printf("請輸入一組數，每個數之間以1個空格隔開，Enter鍵結束輸入\n");
34 int arr[MAXN]; //定義一個足夠大的數組
35 int i=0,j,k,count = 0;
36 while(count<MAXN) //讀入數組，存入數組a中；
37 {
38 scanf("%d",&arr[i++]);
39 count++;
40 if(getchar() == '\n') break;
41 }
42 QuickSort(arr,count);
43 for(i=0;i<count;i++)
44 printf("%d ",arr[i]);
45 return 0;
46 }
<--點擊左側+展開
7.歸並排序。
待補充...
8.基數排序。
待補充...
