一. 冒泡排序(BubbleSort)
- 基本思想：兩個(gè)數(shù)比較大小，較大的數(shù)下沉，較小的數(shù)冒起來。
- 過程：
- 比較相鄰的兩個(gè)數(shù)據(jù)，如果第二個(gè)數(shù)小，就交換位置。
- 從后向前兩兩比較，一直到比較最前兩個(gè)數(shù)據(jù)。最終最小數(shù)被交換到起始的位置，這樣第一個(gè)最小數(shù)的位置就排好了。
-
繼續(xù)重復(fù)上述過程，依次將第2.3...n-1個(gè)最小數(shù)排好位置。
冒泡排序.png
- 平均時(shí)間復(fù)雜度：O(n2)
- java代碼實(shí)現(xiàn)：
其實(shí)冒泡排序，外層執(zhí)行n次循環(huán)，內(nèi)層執(zhí)行n-1-i次循環(huán)，n是元素個(gè)數(shù)
將最小的數(shù)字移動(dòng)到最前面，從最后面開始移動(dòng)
public static void BubbleSort(int [] arr){
int temp;//臨時(shí)變量
for(int i=0; i<arr.length-1; i++){ //表示趟數(shù)，一共arr.length-1次。
for(int j=arr.length-1; j>i; j--){
if(arr[j] < arr[j-1]){
temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
}
}
}
}
}
//冒泡排序?qū)崿F(xiàn)-將大的數(shù)字移動(dòng)到最后面
for(int i=0;i<a.length-1;i++){
for(int j=0;j<a.length-i-1;j++){
if(a[j]>a[j+1]){
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
1. 優(yōu)化：
- 針對問題： 數(shù)據(jù)的順序排好之后，冒泡算法仍然會(huì)繼續(xù)進(jìn)行下一輪的比較，直到arr.length-1次，后面的比較沒有意義的。
- 方案： 設(shè)置標(biāo)志位flag，如果發(fā)生了交換flag設(shè)置為true；如果沒有交換就設(shè)置為false。 這樣當(dāng)一輪比較結(jié)束后如果flag仍為false，即：這一輪沒有發(fā)生交換，說明數(shù)據(jù)的順序已經(jīng)排好，沒有必要繼續(xù)進(jìn)行下去。
public static void BubbleSort1(int [] arr){
int temp;//臨時(shí)變量
boolean flag;//是否交換的標(biāo)志
for(int i=0; i<arr.length-1; i++){ //表示趟數(shù)，一共arr.length-1次。
flag = false;
for(int j=arr.length-1; j>i; j--){
if(arr[j] < arr[j-1]){
temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
flag = true;
}
}
if(!flag) break;
}
}
}
二. 選擇排序(SelctionSort)
基本思想： 在長度為N的無序數(shù)組中，第一次遍歷n-1個(gè)數(shù)，找到最小的數(shù)值與第一個(gè)元素交換； 第二次遍歷n-2個(gè)數(shù)，找到最小的數(shù)值與第二個(gè)元素交換； 。。。 第n-1次遍歷，找到最小的數(shù)值與第n-1個(gè)元素交換，排序完成。
-
過程：
選擇排序.png 平均時(shí)間復(fù)雜度：O(n2)
java代碼實(shí)現(xiàn)：
public static void select_sort(int array[],int length){
for(int i=0;i<length-1;i++){
int minIndex = i;
// 每次內(nèi)部循環(huán)找到最小的元素位置
for(int j=i+1;j<length;j++){
if(array[j]<array[minIndex]){
minIndex = j;
}
}
// 交換第i個(gè)元素和最小元素的位置
if(minIndex != i){
int temp = array[i];
array[i] = array[minIndex];
array[minIndex] = temp;
}
}
}
三. 插入排序(Insertion Sort)
- 基本思想： 在要排序的一組數(shù)中，假定前n-1個(gè)數(shù)已經(jīng)排好序，現(xiàn)在將第n個(gè)數(shù)插到前面的有序數(shù)列中，使得這n個(gè)數(shù)也是排好順序的。如此反復(fù)循環(huán)，直到全部排好順序。
插入排序，其實(shí)就是一直進(jìn)行兩兩相連元素的比較交換，最外層進(jìn)行n次，內(nèi)層依次進(jìn)行1次，2次。。。n-1次 -
過程：
插入排序.png
相同的場景
- 平均時(shí)間復(fù)雜度：O(n2)
- java代碼實(shí)現(xiàn)：
public static void insert_sort(int array[],int lenth){
int temp;
for(int i=0;i<lenth-1;i++){
for(int j=i+1;j>0;j--){
if(array[j] < array[j-1]){
temp = array[j-1];
array[j-1] = array[j];
array[j] = temp;
}else{ //不需要交換
break;
}
}
}
}
從大到小排序，與上面只有if判斷執(zhí)行體不同
public static void insertSort(int[] array){
int temp;
for (int i=0;i<array.length-1;i++){
for (int j=i+1;j>0;j--){
if (array[j]>array[j-1]){
temp = array[j-1];
array[j-1] = array[j];
array[j] = temp;
} else {
break;
}
}
}
}
四. 希爾排序(Shell Sort)
前言： 數(shù)據(jù)序列1： 13-17-20-42-28 利用插入排序，13-17-20-28-42. Number of swap:1; 數(shù)據(jù)序列2： 13-17-20-42-14 利用插入排序，13-14-17-20-42. Number of swap:3; 如果數(shù)據(jù)序列基本有序，使用插入排序會(huì)更加高效。
基本思想： 在要排序的一組數(shù)中，根據(jù)某一增量分為若干子序列，并對子序列分別進(jìn)行插入排序。 然后逐漸將增量減小,并重復(fù)上述過程。直至增量為1,此時(shí)數(shù)據(jù)序列基本有序,最后進(jìn)行插入排序。
-
過程：
希爾排序.png
希爾排序
- 平均時(shí)間復(fù)雜度：O(NlogN)
- java代碼實(shí)現(xiàn)：
public static void shell_sort(int array[],int lenth){
int temp = 0;
int incre = lenth;
while(true){
incre = incre/2;
for(int k = 0;k<incre;k++){ //根據(jù)增量分為若干子序列
// 內(nèi)部是使用插入排序
for(int i=k+incre;i<lenth;i+=incre){
// 每次都是使用當(dāng)前排序的次數(shù)的后一位數(shù)往前比較
for(int j=i;j>k;j-=incre){
if(array[j]<array[j-incre]){
temp = array[j-incre];
array[j-incre] = array[j];
array[j] = temp;
}else{
break;
}
}
}
}
if(incre == 1){
break;
}
}
}
/**
* 希爾排序
* @param arrays 需要排序的序列
*/
public static void sort(int[] arrays){
if(arrays == null || arrays.length <= 1){
return;
}
//增量
int incrementNum = arrays.length/2;
while(incrementNum >=1){
for(int i=0;i<arrays.length;i++){
//進(jìn)行插入排序
for(int j=i;j<arrays.length-incrementNum;j=j+incrementNum){
if(arrays[j]>arrays[j+incrementNum]){
int temple = arrays[j];
arrays[j] = arrays[j+incrementNum];
arrays[j+incrementNum] = temple;
}
}
}
//設(shè)置新的增量
incrementNum = incrementNum/2;
}
}
五. 快速排序(Quicksort)
1. 基本思想：（分治）
- 先從數(shù)列中取出一個(gè)數(shù)作為key值；
- 將比這個(gè)數(shù)小的數(shù)全部放在它的左邊，大于或等于它的數(shù)全部放在它的右邊；
- 對左右兩個(gè)小數(shù)列重復(fù)第二步，直至各區(qū)間只有1個(gè)數(shù)。
1. 輔助理解：
- 初始時(shí) i = 0; j = 9; key=72
由于已經(jīng)將a[0]中的數(shù)保存到key中，可以理解成在數(shù)組a[0]上挖了個(gè)坑，可以將其它數(shù)據(jù)填充到這來。
從j開始向前找一個(gè)比key小的數(shù)。當(dāng)j=8，符合條件，a[0] = a[8] ; i++ ; 將a[8]挖出再填到上一個(gè)坑a[0]中。
這樣一個(gè)坑a[0]就被搞定了，但又形成了一個(gè)新坑a[8]，這怎么辦了？簡單，再找數(shù)字來填a[8]這個(gè)坑。
這次從i開始向后找一個(gè)大于key的數(shù)，當(dāng)i=3，符合條件，a[8] = a[3] ; j-- ; 將a[3]挖出再填到上一個(gè)坑中。
變化之前的數(shù)組：72 - 6 - 57 - 88 - 60 - 42 - 83 - 73 - 48 - 85
0 1 2 3 4 5 6 7 8 9
此時(shí) i = 3; j = 7; key=72
再重復(fù)上面的步驟，先從后向前找，再從前向后找。
從j開始向前找，當(dāng)j=5，符合條件，將a[5]挖出填到上一個(gè)坑中，a[3] = a[5]; i++;
從i開始向后找，當(dāng)i=5時(shí)，由于i==j退出。
此時(shí)，i = j = 5，而a[5]剛好又是上次挖的坑，因此將key填入a[5]。
變化之前的數(shù)組：48 - 6 - 57 - 88 - 60 - 42 - 83 - 73 - 88 - 85
0 1 2 3 4 5 6 7 8 9
這里的i=3的位置，因?yàn)橹皩⒅蒂x值給了i=8的位置，所以這里還沒改變可以看出a[5]前面的數(shù)字都小于它，a[5]后面的數(shù)字都大于它。因此再對a[0…4]和a[6…9]這二個(gè)子區(qū)間重復(fù)上述步驟就可以了。
上一步得到的結(jié)果數(shù)組：48 - 6 - 57 - 42 - 60 - 72 - 83 - 73 - 88 - 85
0 1 2 3 4 5 6 7 8 9
3. 平均時(shí)間復(fù)雜度：O(N*logN)
快速排序中，基值key為序列的最大元素或者最小元素時(shí)，是最壞情況，時(shí)間復(fù)雜度為O(N^2)
4. 代碼實(shí)現(xiàn)：
public static void quickSort(int a[],int l,int r){
if(l>=r)
return;
int i = l; int j = r; int key = a[l];//選擇第一個(gè)數(shù)為key
while(i<j){
while(i<j && a[j]>=key)//從右向左找第一個(gè)小于key的值
j--;
if(i<j){
a[i] = a[j];
i++;
}
while(i<j && a[i]<key)//從左向右找第一個(gè)大于key的值
i++;
if(i<j){
a[j] = a[i];
j--;
}
}
//i == j
a[i] = key;
quickSort(a, l, i-1);//遞歸調(diào)用
quickSort(a, i+1, r);//遞歸調(diào)用
}
key值的選取可以有多種形式，例如中間數(shù)或者隨機(jī)數(shù)，分別會(huì)對算法的復(fù)雜度產(chǎn)生不同的影響。
5.快速排序優(yōu)化
具體可以查看快速排序優(yōu)化https://blog.csdn.net/weizhengbo/article/details/77618963
//三數(shù)取中法：
//快速排序需要找基準(zhǔn)值，為了避免找的基準(zhǔn)值是最大的數(shù)，或者是最小的數(shù)，（基準(zhǔn)值最大或者最小，效率最差）
//快速排序可用三數(shù)取中法優(yōu)化，以下是三數(shù)取中法代碼:
int ThreeToMid(int a, int b, int c)//1 3 5
{
if (a>b)
{
if (b > c)
return b;
else
{
if (a < c)
return a;
else
return c;
}
}
else
{
if (b < c)
return b;
else
{
if (a>c)
return a;
else
return c;
}
}
}
快速排序適用于數(shù)據(jù)雜亂無章的場景，而且越亂，快速排序的效率越體現(xiàn)的淋漓盡致。
六. 歸并排序(Merge Sort)
1. 基本思想：
歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法的一個(gè)非常典型的應(yīng)用。
首先考慮下如何將2個(gè)有序數(shù)列合并。這個(gè)非常簡單，只要從比較2個(gè)數(shù)列的第一個(gè)數(shù)，誰小就先取誰，取了后就在對應(yīng)數(shù)列中刪除這個(gè)數(shù)。然后再進(jìn)行比較，如果有數(shù)列為空，那直接將另一個(gè)數(shù)列的數(shù)據(jù)依次取出即可。
//將有序數(shù)組a[]和b[]合并到c[]中
void MemeryArray(int a[], int n, int b[], int m, int c[])
{
int i, j, k;
i = j = k = 0;
while (i < n && j < m)
{
if (a[i] < b[j])
c[k++] = a[i++];
else
c[k++] = b[j++];
}
while (i < n)
c[k++] = a[i++];
while (j < m)
c[k++] = b[j++];
}
解決了上面的合并有序數(shù)列問題，再來看歸并排序，其的基本思路就是將數(shù)組分成2組A，B，如果這2組組內(nèi)的數(shù)據(jù)都是有序的，那么就可以很方便的將這2組數(shù)據(jù)進(jìn)行排序。如何讓這2組組內(nèi)數(shù)據(jù)有序了？
可以將A，B組各自再分成2組。依次類推，當(dāng)分出來的小組只有1個(gè)數(shù)據(jù)時(shí)，可以認(rèn)為這個(gè)小組組內(nèi)已經(jīng)達(dá)到了有序，然后再合并相鄰的2個(gè)小組就可以了。這樣通過先遞歸的分解數(shù)列，再合并數(shù)列就完成了歸并排序。
2. 過程：
3. 平均時(shí)間復(fù)雜度：O(NlogN) 歸并排序的效率是比較高的，設(shè)數(shù)列長為N，將數(shù)列分開成小數(shù)列一共要logN步，每步都是一個(gè)合并有序數(shù)列的過程，時(shí)間復(fù)雜度可以記為O(N)，故一共為O(N*logN)。
4. 代碼實(shí)現(xiàn)：
public static void merge_sort(int a[],int first,int last,int temp[]){
if(first < last){
int middle = (first + last)/2;// 找中間位置
merge_sort(a,first,middle,temp);//左半部分排好序
merge_sort(a,middle+1,last,temp);//右半部分排好序
mergeArray(a,first,middle,last,temp); //合并左右部分
}
}
//合并 ：將兩個(gè)序列a[first-middle],a[middle+1-end]合并
public static void mergeArray(int a[],int first,int middle,int end,int temp[]){
int i = first;
int m = middle;
int j = middle+1;
int n = end;
int k = 0;
while(i<=m && j<=n){
if(a[i] <= a[j]){
temp[k] = a[i];
k++;
i++;
}else{
temp[k] = a[j];
k++;
j++;
}
}
while(i<=m){
temp[k] = a[i];
k++;
i++;
}
while(j<=n){
temp[k] = a[j];
k++;
j++;
}
for(int ii=0;ii<k;ii++){
a[first + ii] = temp[ii];
}
}
按8位數(shù)字的序列舉例：初始first=0，middle=3，end=7
那么第一個(gè)排序之后，分成兩個(gè)序列調(diào)用：
（1）first=0，end=3，middle=1
first=0，end=1，middle=0
first=0，end=0
first=1，end=0
first=2，end=3，middle=2
first=2，end=2
first=3，end=3
（2）first=4，end=7，middle=5
first=4，end=5，middle=4
first=4，end=4
first=5，end=5
first=6，end=7，middle=6
first=6，end=6
first=7，end=7
最終的是排序當(dāng)個(gè)數(shù)字的，然后將兩個(gè)序列合并，依次從最終序列開始，依次將兩個(gè)序列合并
七. 堆排序(HeapSort)
1. 基本思想：
2. ** 圖示：** （88,85,83,73,72,60,57,48,42,6）
Heap Sort
3. 平均時(shí)間復(fù)雜度：O(NlogN)
由于每次重新恢復(fù)堆的時(shí)間復(fù)雜度為O(logN)，共N - 1次重新恢復(fù)堆操作，再加上前面建立堆時(shí)N / 2次向下調(diào)整，每次調(diào)整時(shí)間復(fù)雜度也為O(logN)。二次操作時(shí)間相加還是O(N * logN)。
4. java代碼實(shí)現(xiàn)：
//構(gòu)建最小堆
public static void MakeMinHeap(int a[], int n){
for(int i=(n-1)/2 ; i>=0 ; i--){
MinHeapFixdown(a,i,n);
}
}
//從i節(jié)點(diǎn)開始調(diào)整,n為節(jié)點(diǎn)總數(shù) 從0開始計(jì)算 i節(jié)點(diǎn)的子節(jié)點(diǎn)為 2*i+1, 2*i+2
public static void MinHeapFixdown(int a[],int i,int n){
int j = 2*i+1; //子節(jié)點(diǎn)
int temp = 0;
while(j<n){
//在左右子節(jié)點(diǎn)中尋找最小的
if(j+1<n && a[j+1]<a[j]){
j++;
}
if(a[i] <= a[j])
break;
//較大節(jié)點(diǎn)下移
temp = a[i];
a[i] = a[j];
a[j] = temp;
i = j;
j = 2*i+1;
}
}
public static void MinHeap_Sort(int a[],int n){
int temp = 0;
MakeMinHeap(a,n);
for(int i=n-1;i>0;i--){
temp = a[0];
a[0] = a[i];
a[i] = temp;
MinHeapFixdown(a,0,i);
}
}
八. 基數(shù)排序(RadixSort)
BinSort
1. 基本思想：
BinSort想法非常簡單，首先創(chuàng)建數(shù)組A[MaxValue]；然后將每個(gè)數(shù)放到相應(yīng)的位置上（例如17放在下標(biāo)17的數(shù)組位置）；最后遍歷數(shù)組，即為排序后的結(jié)果。O(M*N)
2. ** 圖示：**
3. ** 問題：** 當(dāng)序列中存在較大值時(shí)，BinSort 的排序方法會(huì)浪費(fèi)大量的空間開銷。
RadixSort
1. 基本思想：
基數(shù)排序是在BinSort的基礎(chǔ)上，通過基數(shù)的限制來減少空間的開銷。
2. 過程：
過程1
過程2
（1）首先確定基數(shù)為10，數(shù)組的長度也就是10.每個(gè)數(shù)34都會(huì)在這10個(gè)數(shù)中尋找自己的位置。
（2）不同于BinSort會(huì)直接將數(shù)34放在數(shù)組的下標(biāo)34處，基數(shù)排序是將34分開為3和4，第一輪排序根據(jù)最末位放在數(shù)組的下標(biāo)4處，第二輪排序根據(jù)倒數(shù)第二位放在數(shù)組的下標(biāo)3處，然后遍歷數(shù)組即可。
3. java代碼實(shí)現(xiàn)：
public static void RadixSort(int A[],int temp[],int n,int k,int r,int cnt[]){
//A:原數(shù)組
//temp:臨時(shí)數(shù)組
//n:序列的數(shù)字個(gè)數(shù)
//k:最大的位數(shù)2
//r:基數(shù)10
//cnt:存儲(chǔ)bin[i]的個(gè)數(shù)
for(int i=0 , rtok=1; i<k ; i++ ,rtok = rtok*r){
//初始化
for(int j=0;j<r;j++){
cnt[j] = 0;
}
//計(jì)算每個(gè)箱子的數(shù)字個(gè)數(shù)
for(int j=0;j<n;j++){
cnt[(A[j]/rtok)%r]++;
}
//cnt[j]的個(gè)數(shù)修改為前j個(gè)箱子一共有幾個(gè)數(shù)字
for(int j=1;j<r;j++){
cnt[j] = cnt[j-1] + cnt[j];
}
for(int j = n-1;j>=0;j--){ //重點(diǎn)理解
cnt[(A[j]/rtok)%r]--;
temp[cnt[(A[j]/rtok)%r]] = A[j];
}
for(int j=0;j<n;j++){
A[j] = temp[j];
}
}
}
九.排序總結(jié)
拿｛ 6，2，4，6，1｝舉例。
有兩個(gè)6，a[0]和a[3]。排序結(jié)果就有兩種可能：
如果排序結(jié)束后，a[0]可以保證一定在a[3]前頭，也就是他們原有的順序不變，那這種排序算法就是穩(wěn)定的。（比如常見的冒泡排序、基數(shù)排序、插入排序、歸并排序、桶排序、二叉樹排序等都是穩(wěn)定的排序算法）
反之，如果不能保證原有順序，這種算法就是不穩(wěn)定的。（比如常見的選擇排序，希爾排序，堆排序，快速排序等都是不穩(wěn)定的排序算法）
十.穩(wěn)定性分析：
冒泡排序：穩(wěn)定
將n個(gè)記錄看作按縱向排列，每趟排序時(shí)自下至上對每對相鄰記錄進(jìn)行比較，若次序不符合要求（逆序）就交換。每趟排序結(jié)束時(shí)都能使排序范圍內(nèi)關(guān)鍵字最小的記錄象一個(gè)氣泡一樣升到表上端的對應(yīng)位置，整個(gè)排序過程共進(jìn)行n-1趟，依次將關(guān)鍵字最小、次小、第三小…的各個(gè)記錄“冒到”表的第一個(gè)、第二個(gè)、第三個(gè)… 位置上。
如：從小到大排序，那么算法就是從第一個(gè)開始，依次拿第一個(gè)、第二個(gè)往后做對比，前一個(gè)小于后一個(gè)，則不交換位置，大于后一個(gè)則交換位置，等于的也不交換位置。因此是穩(wěn)定的
選擇排序：不穩(wěn)定
顧名思意,就是直接從待排序數(shù)組里選擇一個(gè)最小(或最大)的數(shù)字,每次都拿一個(gè)最小數(shù)字出來,順序放入新數(shù)組,直到全部拿完。再簡單點(diǎn),對著一群數(shù)組說,你們誰最小出列,站到最后邊,然后繼續(xù)對剩余的無序數(shù)組說,你們誰最小出列,站到最后邊,再繼續(xù)剛才的操作,一直到最后一個(gè),繼續(xù)站到最后邊,現(xiàn)在數(shù)組有序了,從小到大。
選擇排序的做法是從第一個(gè)位置開始，依次拿第一個(gè)、第二個(gè)、第三個(gè)到第N個(gè)去與后面做對比，找到后面最小的一個(gè)，做位置交換。那么這樣的做法，就會(huì)可能造成相同的數(shù)字位置前后出現(xiàn)交換的情況。
例如：5 8 5 2 9這個(gè)數(shù)列，第一次拿第一個(gè)5去與后面的做比較，后面最小的是2，那么5跟2做比較，交換位置。
插入排序：穩(wěn)定
插入排序就是每一步都將一個(gè)待排數(shù)據(jù)按其大小插入到已經(jīng)排序的數(shù)據(jù)中的適當(dāng)位置，直到全部插入完畢。插入排序方法分直接插入排序和折半插入排序兩種。折半插入排序基本思想和直接插入排序一樣，區(qū)別在于尋找插入位置的方法不同，折半插入排序采用折半查找法來尋找插入位置。折半查找法只能對有序的序列使用。基本思想就是查找插入位置的時(shí)候，把序列分成兩半（選擇一個(gè)中間數(shù)mid），如果帶插入數(shù)據(jù)大于mid則到右半部分序列去在進(jìn)行折半查找；反之，則到左半部分序列去折半查找。
第n次排序，待排序是第n+1個(gè)數(shù)字，那么就拿這個(gè)數(shù)字向前去做比較，只要是小于前面一個(gè)數(shù)字，就往前面交換，直到前面一個(gè)數(shù)字小于這個(gè)數(shù)字為止。那么如果兩個(gè)數(shù)字是一樣的，就不會(huì)發(fā)生位置交換的情況，那么就是穩(wěn)定的。
其實(shí)插入排序，就是在第n+1個(gè)數(shù)字去與前面的數(shù)字做比較，從后往前比較，根據(jù)需要將更小的或者更大的往前移動(dòng)。因?yàn)槭菑牡趎+1個(gè)數(shù)字開始去比較排序插入的，因此第一個(gè)數(shù)字可以忽略，所以是排length-1次。
快速排序：不穩(wěn)定
通過一趟掃描將要排序的數(shù)據(jù)分割成獨(dú)立的兩部分,其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小,然后再按此方法對這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序,整個(gè)排序過程可以遞歸進(jìn)行,以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列
快速排序的做法，就是每一次都將序列的第一個(gè)數(shù)字看成key，然后下標(biāo)為0的看成是i，序列的最后一個(gè)的下標(biāo)看成是j，然后從后向前找出比key小的數(shù)字，這個(gè)時(shí)候j也變成這個(gè)數(shù)字的下標(biāo)，將這個(gè)數(shù)字填入i的位置上，然后再從前向后找到比key大的數(shù)字，填入最新的j的位置上，這個(gè)時(shí)候i的位置也變成了這個(gè)比key大的數(shù)字的下標(biāo)，交換完成之后，繼續(xù)從后向前找小的數(shù)字，從前向后找大的數(shù)字，依次將小的數(shù)字填入i的位置，大的數(shù)字填入最新的j的位置上，直到i==j的時(shí)候，將key填入i的位置上。然后將key的前面的數(shù)字和后面的數(shù)字分別看成是一個(gè)序列，把這兩個(gè)序列重復(fù)上面的步驟。
那么在交換數(shù)字的過程中就可能出現(xiàn)相同數(shù)字順序發(fā)生變化的情況。例如：
24，58，58，22，98這個(gè)序列，i=0，j=4，key=24，那么第一次就是22移動(dòng)到i=0的位置上，第一個(gè)58比24大，移動(dòng)到j(luò)=3的位置上，那么第一個(gè)58和第二個(gè)58的位置就出現(xiàn)了變化，所以不穩(wěn)定。
public static void quickSort(int a[],int l,int r){
if(l>=r)
return;
int i = l; int j = r; int key = a[l];//選擇第一個(gè)數(shù)為key
while(i<j){
while(i<j && a[j]>=key)//從右向左找第一個(gè)小于key的值
j--;
if(i<j){
a[i] = a[j];
i++;
}
while(i<j && a[i]<key)//從左向右找第一個(gè)大于key的值
i++;
if(i<j){
a[j] = a[i];
j--;
}
}
//i == j
a[i] = key;
quickSort(a, l, i-1);//遞歸調(diào)用
quickSort(a, i+1, r);//遞歸調(diào)用
}
歸并排序：穩(wěn)定
把原始數(shù)組分成若干子數(shù)組,對每一個(gè)子數(shù)組進(jìn)行排序,繼續(xù)把子數(shù)組與子數(shù)組合并,合并后仍然有序,直到全部合并完,形成有序的數(shù)組。
歸并序列，是依次將序列二等分，直到分成每個(gè)序列只有一個(gè)數(shù)字為止，然后依次對每個(gè)序列做排序，然后再兩兩合并兩個(gè)序列。這樣的排序合并，當(dāng)出現(xiàn)數(shù)字相同的時(shí)候，并不會(huì)交換順序。
public static void merge_sort(int a[],int first,int last,int temp[]){
if(first < last){
int middle = (first + last)/2;// 找中間位置
merge_sort(a,first,middle,temp);//左半部分排好序
merge_sort(a,middle+1,last,temp);//右半部分排好序
mergeArray(a,first,middle,last,temp); //合并左右部分
}
}
//合并 ：將兩個(gè)序列a[first-middle],a[middle+1-end]合并
public static void mergeArray(int a[],int first,int middle,int end,int temp[]){
int i = first;
int m = middle;
int j = middle+1;
int n = end;
int k = 0;
while(i<=m && j<=n){
if(a[i] <= a[j]){
temp[k] = a[i];
k++;
i++;
}else{
temp[k] = a[j];
k++;
j++;
}
}
while(i<=m){
temp[k] = a[i];
k++;
i++;
}
while(j<=n){
temp[k] = a[j];
k++;
j++;
}
for(int ii=0;ii<k;ii++){
a[first + ii] = temp[ii];
}
}
基數(shù)排序：穩(wěn)定
一個(gè)元素有多個(gè)關(guān)鍵字，定義排序后的“有序”是指依次比較這些關(guān)鍵字，不同的直接按其大小關(guān)系，相同的比較后續(xù)的關(guān)鍵字，例如字符串與數(shù)字。然后，這些關(guān)鍵字都有一些范圍。依次選取這些關(guān)鍵字作為依據(jù)，進(jìn)行依次分類，這樣，類別之間就有了相對的大小關(guān)系。然后，對每個(gè)類別進(jìn)行相同的操作，直至所有關(guān)鍵字都被比較過為止。
基礎(chǔ)排序，就是根據(jù)0-9這十個(gè)基數(shù)，依次針對個(gè)位、十位、百位等做重新排序。
比如個(gè)位的，按順序進(jìn)行，如果個(gè)位為0的，則放在0位上，為1的，放在1位上，依次進(jìn)行，然后從零開始，將所有的數(shù)字重新組合起來，按之前的順序。十位上的也是這樣進(jìn)行，如果沒有百位，則就可以排列好。這樣的情況，如果是兩個(gè)相同的數(shù)字，那么在排序的過程中，順序永遠(yuǎn)不會(huì)發(fā)生改變，因此是穩(wěn)定的。
public static void RadixSort(int A[],int temp[],int n,int k,int r,int cnt[]){
//A:原數(shù)組
//temp:臨時(shí)數(shù)組
//n:序列的數(shù)字個(gè)數(shù)
//k:最大的位數(shù)2
//r:基數(shù)10
//cnt:存儲(chǔ)bin[i]的個(gè)數(shù)
for(int i=0 , rtok=1; i<k ; i++ ,rtok = rtok*r){
//初始化
for(int j=0;j<r;j++){
cnt[j] = 0;
}
//計(jì)算每個(gè)箱子的數(shù)字個(gè)數(shù)
for(int j=0;j<n;j++){
cnt[(A[j]/rtok)%r]++;
}
//cnt[j]的個(gè)數(shù)修改為前j個(gè)箱子一共有幾個(gè)數(shù)字
for(int j=1;j<r;j++){
cnt[j] = cnt[j-1] + cnt[j];
}
for(int j = n-1;j>=0;j--){ //重點(diǎn)理解
cnt[(A[j]/rtok)%r]--;
temp[cnt[(A[j]/rtok)%r]] = A[j];
}
for(int j=0;j<n;j++){
A[j] = temp[j];
}
}
}
希爾排序：不穩(wěn)定
希爾排序的實(shí)質(zhì)就是分組插入排序，該方法又稱縮小增量排序，因DL．Shell于1959年提出而得名。
該方法的基本思想是：先將整個(gè)待排元素序列分割成若干個(gè)子序列（由相隔某個(gè)“增量”的元素組成的）分別進(jìn)行直接插入排序，然后依次縮減增量再進(jìn)行排序，待整個(gè)序列中的元素基本有序（增量足夠?。r(shí)，再對全體元素進(jìn)行一次直接插入排序。因?yàn)橹苯硬迦肱判蛟谠鼗居行虻那闆r下（接近最好情況），效率是很高的，因此希爾排序在時(shí)間效率上比前兩種方法有較大提高。
希爾排序，就是將整個(gè)序列分析若干個(gè)子序列，比如循環(huán)除以2，直到得到余數(shù)為1的時(shí)候，這樣的話，就可以依次取到序列的間隔，就是每個(gè)子序列都只有兩個(gè)數(shù)字，然后交換位置，然后再擴(kuò)大子序列的長度，而每次子序列的排序都是一次插入排序，一次插入排序是穩(wěn)定的，但是多個(gè)不同的序列同時(shí)進(jìn)行插入排序的時(shí)候，就會(huì)有可能造成相同的元素的位置順序改變，所以是不穩(wěn)定的。
public static void shell_sort(int array[],int lenth){
int temp = 0;
int incre = lenth;
while(true){
incre = incre/2;
for(int k = 0;k<incre;k++){ //根據(jù)增量分為若干子序列
for(int i=k+incre;i<lenth;i+=incre){
for(int j=i;j>k;j-=incre){
if(array[j]<array[j-incre]){
temp = array[j-incre];
array[j-incre] = array[j];
array[j] = temp;
}else{
break;
}
}
}
}
if(incre == 1){
break;
}
}
}
堆排序：不穩(wěn)定
堆分為大根堆和小根堆，是完全二叉樹。大根堆的要求是每個(gè)節(jié)點(diǎn)的值都不大于其父節(jié)點(diǎn)的值，即A[PARENT[i]] >= A[i]。在數(shù)組的非降序排序中，需要使用的就是大根堆，因?yàn)楦鶕?jù)大根堆的要求可知，最大的值一定在堆頂。
既然是堆排序，自然需要先建立一個(gè)堆，而建堆的核心內(nèi)容是調(diào)整堆，使二叉樹滿足堆的定義（每個(gè)節(jié)點(diǎn)的值都不大于其父節(jié)點(diǎn)的值）。調(diào)堆的過程應(yīng)該從最后一個(gè)非葉子節(jié)點(diǎn)開始
例子
72,6,57,88,60,42,83,73,48,85
這個(gè)序列，先創(chuàng)建一個(gè)二叉樹，依次將序列上的數(shù)字放置在二叉樹節(jié)點(diǎn)上，當(dāng)這個(gè)過程中，如果有子節(jié)點(diǎn)大于父節(jié)點(diǎn)的，則交換二者的位置，每放置一個(gè)，就得判斷依次子節(jié)點(diǎn)是否大于父節(jié)點(diǎn)，如果是大于的，就立馬交換位置。直到父節(jié)點(diǎn)都是大于子節(jié)點(diǎn)為止。
（1）然后將根節(jié)點(diǎn)和最后一個(gè)節(jié)點(diǎn)的位置交換，再將最后一個(gè)節(jié)點(diǎn)放置在數(shù)組的最后一位，然后重新調(diào)整二叉樹，直到二叉樹的根節(jié)點(diǎn)是剩下的數(shù)字中最大的為止。
（2）繼續(xù)重復(fù)第一步的步驟，將根節(jié)點(diǎn)數(shù)字與最后一個(gè)節(jié)點(diǎn)的數(shù)字交換位置，然后將最后一個(gè)數(shù)字放置在數(shù)組的倒數(shù)第二個(gè)位置上，依次反復(fù)，直到?jīng)]有節(jié)點(diǎn)為止。
