排序的分類可以分為兩種：內排序和外排序。
在排序過程中鞍匾，全部記錄放在內存交洗，則稱為內排序，如果排序過程中要使用外村橡淑，則稱為外排序构拳。這里講的排序都是屬于內排序。
內排序又可以分為以下幾類：
（1）插入排序：直接插入排序，二分法插入排序和希爾排序
（2）選擇排序：簡單選擇排序隐圾，堆排序
（3）交換排序：冒泡排序伍掀，快速排序
（4）歸并排序
（5）基數(shù)排序
一、插入排序
思想：每步將一個待排序的記錄暇藏，按其順序碼大小插入到前面已經排序的字序列的合適位置蜜笤，直到全部插入排序完成為止盐碱。
關鍵問題：在前面已經排序好的序列中找到合適的插入位置县好。
方法：
? 直接插入排序: 直接插入排序是穩(wěn)定的排序晾咪。當文件初態(tài)為正態(tài)，則每個待插入的記錄只需比較一次既能夠找到合適的位置插入，故算法的時間復雜度為O(n)，是最好的情況送淆。如果初態(tài)為反序，則第i個待插入的記錄需要比較i+1次才能找到合適位置诀紊，故時間復雜度為O(n2),這也是平均復雜度。
? 二分插入排序：它的排序方法與直接插入思想一樣，只是找合適位置的方式不同。用二分法可以減少比較的次數(shù)。
? 希爾排序:一次插入排序是穩(wěn)定的休玩，但是在不同的插入排序過程中遥赚，相同的元素可能在各自的插入排序中移動，就會打亂其穩(wěn)定性。希爾排序的時間性能優(yōu)于直接排序。但是它是不穩(wěn)定的排序瞄勾。當n值較小時趾疚，n和n2的區(qū)別也小，所以直接插入排序的時間復雜度最好與最壞差不多魄缚。因此希爾排序經過分組徙硅，所以插入速度較快，后期雖然分組較少，但是經過之前的排序泄隔，使文件已經比較接近有序狀態(tài)暖呕。所以也能提高速度。平均時間復雜度為O（nlogn）
實現(xiàn)：
? -直接插入排序? 從后面向前找到合適位置后插入贷帮。直到序列中的每個元素都插入诲侮。
package com.sort刮便；
public class DirectSort {
public static void main(String [] args){
? ? ? ? ? ? ?int[] a={58,46,59,26,45,57,87,62,12,1,64};
? ? ? ? ? ? ?int tmp;
? ? ? ? ? ? ? ? ? ? ? ? //直接插入排序
? ? ? ? ? ? ? ? ? ? ? ? ?for(int i=1;i<a.length;i++){
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? for(int j=i; j>0;j--){
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? if(a[j]<a[j-1]){
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? tmp=a[j-1]
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? a[j-1]=a[j];
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? a[j]=tmp;
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?}
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? ? for(int i:a){
? ? ? ? ? ? ? ? ? ? ? System.out.print(i+" ");
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?}
? ? ? ? ? ? ? ? }
}
-二分法插入排序?它的比較次數(shù)與帶排序記錄的初始狀態(tài)無關搜贤，僅依賴于記錄的個數(shù)耕陷。當n較大時，比直接插入排序的最大比較次數(shù)少的多猾警。最壞的情況為n2/2筑公，最好的情況為n，平均移動次數(shù)為n2
static public void halfSort(int a[]){
? ? ?for(int i =0;i<a.length;i++){
? ? ? ? ? ? ? int low = 0;
? ? ? ? ? ? ? int high = i;
? ? ? ? ? ? ? int mid = 0;
? ? ? ? ? ? ? int temp = a[i];?
? ? ? ? ? ? ? while(low<=high){
? ? ? ? ? ? ? ?mid=(low+high)/2;
? ? ? ? ? ? ? ? if(a[mid]<temp){
? ? ? ? ? ? ? ? ? ?low=mid+1;
? ? ? ? ? ? ? ? ?}else{
? ? ? ? ? ? ? ? ? ? ? ?high=mid-1;
? ? ? ? ? ? ? ? ? }
? ? ? ? ? ?}
? ? ? ? ?//找到要插入的位置，然后將這個位置以后的元素向后移動
? ? ? ? ? ? ? ? ?for(int j = i -1;j>high;j--){
? ? ? ? ? ? ? ? ? a[j+1]=a[j];
? ? ? ? }
? ? ? ? ? ? ? ? ?a[high+1]=temp;
? ? }
}
-希爾排序?先取一個小于n的整數(shù)d1作為第一個增量掉盅，把文件的全部記錄分成d1個組蔓钟。所有距離為d1的倍數(shù)的記錄放在同一個組中，現(xiàn)在各組內進行直接插入排序；然后取第二個增量d2<d1重復上述的分組和排序。直至所取的增量dt為1.即所有記錄放在同一組中進行直接插入排序位置。其實質是分組的直接插入排序。
public static void sort(int [] arrays){
? ? ? ? ? ? int incrementNum = arrays.length/2;
? ? ? ? ? ? while(incrementNum>=1){
? ? ? ? ?for(int i=0;i<arrays.length;i++){
? ? ? ? ? ? ? ?//進行插入排序
? ? ? for(int j=i;j<arrays.length-incrementNum;j+=incrementNum) ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ?if(arrays[j]>arrays[j+incrementNum]){
? ? ? ? ? ? ? ? ? ? ? ? int temp = arrays[j];
? ? ? ? ? ? ? ? ? ? ? ? arrays[j] = arrays[j+incrementNum];
? ? ? ? ? ? ? ? ? ? ? ? arrays[j+incrementNum] = temp;
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? }
? ? ? ? ? ? ? ?//設置新的增量
? ? ? ? ? ? ? ? incrementNum/=2;
? ? ? }
}
二、選擇排序
思想：每趟從待排序的序列里選擇關鍵字最小的記錄放置到已排序的最前位置。直到全部排完祷嘶。
關鍵問題:在剩余的待排序記錄序列中找到最小關鍵碼記錄嘉汰。
方法：直接選擇排序
簡單選擇排序是不穩(wěn)定的排序。時間復雜度：T(n)=O(n2)
? ? ? ? ? ?堆排序：也是一種不穩(wěn)定的排序方法。堆排序可通過樹形結構保存部分比較結果废累，可減少比較次數(shù)。堆排序的最壞時間復雜度為O(nlogn).因為建初始堆所需的比較次數(shù)較多面哥、所以堆排序不適宜于記錄數(shù)比較少的文件。
? ? ? ? ? ? ? 是一種就地排序算法（不需要額外的存儲空間）
實現(xiàn)：
-直接選擇排序它的在要排序的一組數(shù)中，選出最小的一個數(shù)與第一個位置的數(shù)交換，然后在剩下的數(shù)中再找最小的與第二個位置交換姆蘸。直到最后一個數(shù)和倒數(shù)第二個數(shù)比較為止。這個是按固定的位置放置撒轮，插入排序是挨個比較乞旦。
//是不穩(wěn)定的
public class simpleSelectSort{
? ? ? ? ? ?public static void main(String [] args){
? ? ? ? int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1,8};
? ? ? ? ? ?for(int i = 0;i<a.length;i++){
? ? ? ? ? ? ?int min = a[i];
? ? ? ? ? ? ?int n = i;//最小索引
? ? ? ? ? ? for(int j = i+1;j<a.length;j++){
? ? ? ? ? ? ?if(a[j]<min){
? ? ? ? ? ? //找出最小的數(shù)
? ? ? ? ? ? ? min=a[j];
? ? ? ? ? ? ? n=j;
? ? ? ? ? ?}
? ? ? ?}
? ? ? ? ?a[n] = a[i];//如果更換了最小值，相應的交換了位置
? ? ? ? ?a[i] = min;
}
}
}
-堆排序它是一種屬性選擇排序题山，是對直接選擇排序的一種改進。
由堆的定義可以看出戴甩，堆頂元素必為最大項。完全二叉樹可以很直觀的表示堆的結構。堆頂為根，其它為左子樹诽表、右子樹。初始排序時，將待排序列看作是一棵順序存儲的二叉樹患久，調整它們的存儲順序煮落，使之成為一個堆琅拌，堆的根節(jié)點的數(shù)最大。然后將根節(jié)點與堆的最后一個節(jié)點交換，然后前面剩下的n-1個元素再去構成一個堆。以此類推周崭，直到只剩兩個節(jié)點的堆，將它們作交換，得到一個n個節(jié)點的有序排列。從算法來看请祖，堆排序需要經過兩個過程过牙，一蚁袭、建立堆客给，二收夸、是堆頂與最后一個元素交換位置坑匠。所以堆排序由兩個函數(shù)組成。一個是建立堆的滲透函數(shù)卧惜，一個是反復調用滲透函數(shù)實現(xiàn)排序的函數(shù)笛辟。
在這里首先學習一下，大頂堆的實現(xiàn)序苏。堆的建立在堆排序里是至關重要的。除了最后一層捷凄，其它層都是填滿的忱详，也正是因為這樣，樹里面每個節(jié)點的子女和雙親節(jié)點的序號都可以根據(jù)當前節(jié)點的序號直接求出跺涤。
parent（i）=i/2
Left(i)=2*i
right(i)=2*i+1
最大堆的性質就是匈睁，根節(jié)點值大于所有子節(jié)點，我們構建最大堆的操作桶错，對于每個節(jié)點i航唆，我們觀察它的子節(jié)點的大小，如果它小于某個子節(jié)點院刁， 那么則進行位置調換糯钙。然后在相應的子節(jié)點上同樣進行這樣的操作。直到比所有的子節(jié)點都大為止。
三任岸、交換排序
-冒泡排序?在要排序的一組數(shù)中再榄，對當前還未排好序的范圍內的全部數(shù)，自上而下對相鄰的兩個數(shù)一次進行比較和調整享潜，讓較大的數(shù)往下沉困鸥，較小的向上冒。每當兩相鄰的數(shù)比較后剑按，發(fā)現(xiàn)與排序要求相反時疾就，就將它們互換。
冒泡最好復雜度是O(n),最差是O(n2),這也是平均時間復雜度艺蝴。
public class Maopao{
public static void main(String [] args){
? ? ? ? ? ? ? int[] a= {49,38,65,97,76,13,27,49,78,34,12,64,1,8};
? ? ? ? ? ? ? for(int i = 0;i<a.length){
? ? ? ? ? ? ? ? ? ? ? ? ? ? ?for(int j = 0;j<a.length-i-1;j++){
? //這里-i主要是每遍歷一次都把最大的i個數(shù)沉到最底下去了猬腰， ? ? 沒有必要再替換了
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?if(a[j]>a[j+1]){
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?//一次次遍歷后，最大的數(shù)就到最后去了
? ? ? ? ? ? ? ? ? ? ? ? ? ? ?int temp = a[j+1];
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? a[j+1]=a[j];
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? a[j]=temp;
}
}
}
}
}
-快速排序 選擇一個基準元素吴趴，通常選擇第一個元素或者最后一個元素漆诽，通過一趟掃描，將待排序列分成兩部分锣枝，一部分都比基準元素大或等于厢拭，一部分都比基準元素小。這時基準元素就處在了正確的位置撇叁。然后用同樣的方法遞歸的排序劃分的兩部分供鸠。快速排序也是不穩(wěn)定的陨闹。
public static void sort(int a[],int low,int high){
int index=a[low];
while(low<high){
index = a[low];//用子表的第一個記錄做基準
while(low<high&&a[high]>=index){
? ? ? ? ? ?high--;
}
a[low]=array[high];
}
while(a[low]<=index&&high>low){
? ? ? ? ?lo++;
}
a[high]=a[low];
}
array[high]=key;
return hi;
}
public static void sort(int[] array,int low,int high){
?int inidex=partition(array,low,high);
sort(array,low,index-1);
sort(array,index+1,hi);
}
四楞捂、歸并排序
-歸并排序?歸并排序法是把兩個或兩個以上的有序表合并成一個新的有序表，即把待排序序列分為若干個子序列趋厉，每個子序列都是有序的寨闹。然后把有序子序列合并為整體有序序列。歸并排序是穩(wěn)定的排序方法君账，歸并序列的復雜度為O(nlogn)繁堡。速度僅次于快速排序，為穩(wěn)定排序算法乡数，一般用于總體無序椭蹄，但是各子項相對有序的數(shù)列。
public class MergeSort{
public static void main (String [] args){
int [] a={49,38,65,97,76,13,27,49,78,34,12,64,1,8};
//歸并排序
mergeSort(a,0,a.length-1);
for(int i =0;i<a.length;i++){
System.out.print(a[i]+" ");
}
}
private static void mergeSort(int[] a,int left,int right){
if(left<right){
int middle = (left+right)/2;
//對左邊遞歸
mergeSort(a,left,middle);
//對右邊遞歸
mergeSort(a,middle+1,right);
//合并
merge(a,left,middle,right);
}
}
private static void merge(int[] a,int left,int middle, int right){
int[] tmpArr = new int[a.length];
int mid= middle+1;//右邊的起始位置
int tmp = left;
int third = left;
while(left<=middle&&mid<=right){
//從兩個數(shù)組中選取較小的數(shù)放入中間數(shù)組
if(a[left]<=a[mid]){
tmpArr[third++] = a[left++];
}else{
tmpArr[third++]=a[mid++];
}
}
//將剩余的部分放入中間數(shù)組
while(left<=middle){
tmpArr[third++] = a[left++];
}
while(mid<=right){
tmpArr[third++]=a[mid++];
}
//將中間數(shù)組復制回原數(shù)組
while(tmp<=right){
a[tmp] = tmpArr[tmp++];
}
}
}
五净赴、基數(shù)排序
-基數(shù)排序 將所有待比較數(shù)值（正整數(shù)）統(tǒng)一為同樣的數(shù)位長度绳矩，數(shù)位較短者的前面補零。然后從最低位開始玖翅，依次進行一次排序翼馆。這樣從最低位到最高位排序完成后割以，數(shù)列就變成了一個有序數(shù)列⌒赐祝基數(shù)排序是穩(wěn)定的排序算法拳球，基數(shù)排序的時間復雜度為O(d(n+r)),d為位數(shù)，r為基數(shù)珍特。
public class baseSort{
public static void main(String[] args){
int[] a={49,38,65,97,176,213,227,49,78,34,12,164,11,18,1};
sort(a);
}
private static void sort(int[] array){
//找到最大數(shù)祝峻，確定要排序幾趟
int max = 0;
for(int i = 0;i<array.length;i++){
if(max<array[i]){
max=array[i];
}
}
//判斷位數(shù)
int times = 0;
while(max>0){
max = max/10;
times++;
}
//建立十個隊列
List<ArrayList> queue = new ArrayList<ArrayList>();
for(int i = 0;i<10;i++){
ArrayList queue1 = new ArrayList();
queue.add(queue1);
}
//進行times次分配和收集
for(int i=0;i<times;i++){
//分配
for(int j=0;j<array.length;j++){
int x = array[j]%(int)Math.pow(10,i+1)/(int)Math.pow(10,i);
ArrayList queue2 = queue.get(x);
queue2.add(array[j]);
queue.set(x,queue2);
}
//收集
intcount = 0;
for(intj = 0; j < 10; j++) {
while(queue.get(j).size()>0){
ArrayList queue3 =queue.get(j);
array[count] = queue3.get(0);
queue3.remove(0);
count++;
}
}
}
}
}
總結：
一、穩(wěn)定性
穩(wěn)定：冒泡排序扎筒，基數(shù)排序莱找，歸并排序，插入排序
不穩(wěn)定：希爾排序嗜桌，選擇排序奥溺，快速排序，堆排序
二骨宠、平均時間復雜度
O(n^2):直接插入排序浮定，簡單選擇排序，冒泡拍戲
在數(shù)據(jù)規(guī)模較小時（9w內）层亿，直接插入排序桦卒，簡單選擇排序差不多。當數(shù)據(jù)較大時匿又，冒泡排序算法的時間代價最高方灾。這種算法基本是穩(wěn)定
O(nlogn):快速排序，歸并排序碌更，希爾排序裕偿，堆排序
其中快速排序是最好的，其次是歸并和希爾痛单，堆排序在數(shù)據(jù)量很大時嘿棘，效果明顯。
三旭绒、排序算法的選擇
1.數(shù)據(jù)規(guī)模較小時
（1）待排序列基本序的情況下蔫巩，可以選擇直接插入排序
（2）對穩(wěn)定性不作要求宜用簡單選擇排序，對穩(wěn)定性有要求宜用插入或冒泡快压。
2.數(shù)據(jù)規(guī)模很大時
（1）對穩(wěn)定性有要求，可考慮歸并排序
（2）對穩(wěn)定性沒有要求垃瞧，宜用堆排序
3.數(shù)據(jù)規(guī)模適中
（1）完全可以用內存空間蔫劣，序列雜亂，對穩(wěn)定性沒有要求个从，快速排序脉幢，此時要付出log(N)的額外空間歪沃。
（2）序列本身可能有序，對穩(wěn)定性有要求嫌松，空間允許下沪曙，宜用歸并排序。
4.序列初始基本有序（正序）萎羔，宜用直接插入或冒泡液走。
更新鞏固
1.幾乎有序的時候，快排的時間復雜度退化到O(n*n)贾陷，無序的時候快速排序才是比較快缘眶。這個時候采用堆排序是最省時間的。
2.歸并排序在任何時候的時間復雜度均為O(N*logN)髓废，空間復雜度為O(N)巷懈；但是需要建立一個棧來維護，快排在最好的情況下時間復雜度為O(N*logN)慌洪《パ啵空間復雜度為O(logN)
3.希爾排序是縮小增量排序，所以對于初始序列有序還是無序沒有直接關系冈爹。
