一:插入算法
1.1直接插入算法
思想：每次將一個(gè)待排序的數(shù)據(jù)按照其關(guān)鍵字的大小插入到前面已經(jīng)排序好的數(shù)據(jù)中的適當(dāng)位置，直到全部數(shù)據(jù)排序完成。
時(shí)間復(fù)雜度：O(n^2) O(n) O(n^2) （最壞 最好 平均）
空間復(fù)雜度：O(1)
穩(wěn)定性： 穩(wěn)定 每次都是在前面已排好序的序列中找到適當(dāng)?shù)奈恢?，只有小的?shù)字會(huì)往前插入，所以原來(lái)相同的兩個(gè)數(shù)字在排序后相對(duì)位置不變。
代碼實(shí)現(xiàn)
public void insertSort(int [] array){
for (int i=1;i<array.length;i++){
int val = array[i];
int j=i;
while(j>0&&val<array[j-1]){//往前找，直到找到比val小的元素，不然就查到最前面
array[j]=array[j-1];//不滿足就把前面的數(shù)據(jù)往后移動(dòng)
j--;
}
array[j]=val;
}
}
1.2 希爾排序
思想：希爾排序根據(jù)增量值對(duì)數(shù)據(jù)按下標(biāo)進(jìn)行分組，對(duì)每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關(guān)鍵詞越來(lái)越多，當(dāng)增量減至1時(shí)，整體采用直接插入排序得到有序數(shù)組，算法終止。
時(shí)間復(fù)雜度：O(n2) O(n) O(n1.5) （最壞，最好，平均）
空間復(fù)雜度：O(1)
穩(wěn)定性：不穩(wěn)定 因?yàn)槭欠纸M進(jìn)行直接插入排序，原來(lái)相同的兩個(gè)數(shù)字可能會(huì)被分到不同的組去，可能會(huì)使得后面的數(shù)字會(huì)排到前面，使得兩個(gè)相同的數(shù)字排序前后位置發(fā)生變化。
不穩(wěn)定舉例: 4 3 3 2 按2為增量分組，則第二個(gè)3會(huì)跑到前面
//代碼實(shí)現(xiàn)
public static void shellSort(int[] array) {
int len;
len = array.length / 2; // 分成n/2組
while (len >= 1) {
for (int i = len; i < array.length; ++i) { //對(duì)每組進(jìn)行直接插入排序
int temp = array[i];
int j = i - len;
while (j >= 0 && array[j] > temp) {
array[j + len] = array[j];
j -= len;
}
array[j + len] = temp;
}
len /= 2;
}
}
二 交換排序
2.1.冒泡排序
思想：對(duì)待排序元素的關(guān)鍵字從后往前進(jìn)行多遍掃描，遇到相鄰兩個(gè)關(guān)鍵字次序與排序規(guī)則不符時(shí)，就將這兩個(gè)元素進(jìn)行交換。這樣關(guān)鍵字較小的那個(gè)元素就像一個(gè)泡泡一樣，從最后面冒到最前面來(lái)。
時(shí)間復(fù)雜度：最壞：O(n2) 最好: O(n) 平均: O(n2)
空間復(fù)雜度：O(1)
穩(wěn)定性：穩(wěn)定，相鄰的關(guān)鍵字兩兩比較，如果相等則不交換。所以排序前后的相等數(shù)字相對(duì)位置不變。
代碼：
public void bubbleSort (int [] array){
for(int i = 1;i<array.length;i++){
//每次從最后面到第i-1個(gè)數(shù)中找出最小的給第i-1個(gè)數(shù)
for(int j = array.length-1;j >= i;j--){
if(array[j]<array[j-1]){
int val = array[j];
array[j]=array[j-1];
array[j-1]=val;
}
}
}
}
2.2.快速排序
思想：該算法是分治算法，首先選擇一個(gè)基準(zhǔn)元素,根據(jù)基準(zhǔn)元素將待排序列分成兩部分,一部分比基準(zhǔn)元素小,一部分大于等于基準(zhǔn)元素,此時(shí)基準(zhǔn)元素在其排好序后的正確位置,然后再用同樣的方法遞歸地排序劃分的兩部分?；鶞?zhǔn)元素的選擇對(duì)快速排序的性能影響很大，所有一般會(huì)想打亂排序數(shù)組選擇第一個(gè)元素或則隨機(jī)地從后面選擇一個(gè)元素替換第一個(gè)元素作為基準(zhǔn)元素。
時(shí)間復(fù)雜度：最壞:O(n2) 最好: O(nlogn) 平均: O(nlogn)
空間復(fù)雜度：O(nlogn)用于方法棧
穩(wěn)定性：不穩(wěn)定 快排會(huì)將大于等于基準(zhǔn)元素的關(guān)鍵詞放在基準(zhǔn)元素右邊，加入數(shù)組 1 2 2 3 4 5 選擇第二個(gè)2 作為基準(zhǔn)元素，那么排序后 第一個(gè)2跑到了后面，相對(duì)位置發(fā)生變化。
代碼：
void quickSort(int [] array){
partiton(array,0,array.length-1);
}
void partiton(int[] array, int left, int right) {
if(left<right){
//在left到right中選擇一個(gè)數(shù)把小于這個(gè)數(shù)的放左邊，大于的放右邊，返回這個(gè)數(shù)的角標(biāo)
int p = quickSort(array,left,right);
partiton(array,left,p-1);
partiton(array,p+1,right);
}
}
int quickSort(int[] array, int left, int right) {
int val = array[left];
while (left<right){
//從右邊開(kāi)始掃，比val大的不用管
while (left<right&&array[right]>val){
right--;
}
//如果是遇見(jiàn)比val小的，把他和left置換
if(left<right){
array[left++]=array[right];
}
while (left<right&&array[left]<val){
left++;
}
if (left<right){
array[right--]=array[left];
}
}
array[left]=val;
return left;
}
三 選擇排序
3.1.直接選擇排序
思想：首先在未排序序列中找到最?。ù螅┰?，存放到排序序列的起始位置，然后每次從剩余未排序元素中繼續(xù)尋找最?。ù螅┰胤诺揭雅判蛐蛄械哪┪?。以此類推，直到所有元素均排序完畢
時(shí)間復(fù)雜度：最壞:O(n^2) 最好: O(n^2) 平均: O(n^2)
空間復(fù)雜度：O(1)
穩(wěn)定性：不穩(wěn)定 例如數(shù)組 2 2 1 3 第一次選擇的時(shí)候把第一個(gè)2與1交換使得兩個(gè)2的相對(duì)次序發(fā)生了改變。
代碼：
void selectSort(int [] array ){
for(int i = 0 ;i <= array.length-1;i++){
for(int j = i+1;j<array.length;j++){
if(array[i]>array[j]){
int val = array[i];
array[i]=array[j];
array[j]=val;
}
}
}
}
四.堆排序
思想：堆排序是利用堆的性質(zhì)進(jìn)行的一種選擇排序，先將排序元素構(gòu)建一個(gè)最大堆,每次堆中取出最大的元素并調(diào)整堆。將該取出的最大元素放到已排好序的序列前面。這種方法相對(duì)選擇排序，時(shí)間復(fù)雜度更低，效率更高。
時(shí)間復(fù)雜度：最壞:O(nlog2n) 最好: O(nlog2n) 平均: O(nlog2n)
空間復(fù)雜度：O(1)
穩(wěn)定性：不穩(wěn)定 例如 5 10 15 10。 如果堆頂5先輸出，則第三層的10(最后一個(gè)10)的跑到堆頂，然后堆穩(wěn)定，繼續(xù)輸出堆頂，則剛才那個(gè)10跑到前面了，所以兩個(gè)10排序前后的次序發(fā)生改變。
代碼：
private void heapSort(int[] array) {
//初始化大根堆，從不是葉子節(jié)點(diǎn)的最后一個(gè)節(jié)點(diǎn)開(kāi)始建立大根堆
for(int i = (array.length-1)/2;i>=0;i--){
filterHeap(array,i,array.length);
}
for (int i = array.length-1;i>0;i--){
//每次都把第一個(gè)元素和第i個(gè)元素交換。
int item = array[0];
array[0]=array[i];
array[i]=item;
//再調(diào)整arra[0~i]個(gè)元素，
filterHeap(array,0,i);
}
}
private void filterHeap(int[] array, int root, int length) {
int child = root * 2;
int r = root;
int item;
while (child<length){
//如果右還在比左孩子大 拿右孩子的
if(child+1<length&&array[child]<array[child+1]){
child++;
}
//如果孩子節(jié)點(diǎn)比當(dāng)前節(jié)點(diǎn)大，調(diào)整位置，繼續(xù)走
if(array[r]<array[child]){
item = array[r];
array[r]=array[child];
array[child]=item;
r=child;
child = r*2;
}
else {
break;
}
}
}
五.歸并排序
思想：歸并排序采用了分治算法，首先遞歸將原始數(shù)組劃分為若干子數(shù)組，對(duì)每個(gè)子數(shù)組進(jìn)行排序。然后將排好序的子數(shù)組遞歸合并成一個(gè)有序的數(shù)組。
時(shí)間復(fù)雜度：最壞:O(nlog2n) 最好: O(nlog2n) 平均: O(nlog2n)
空間復(fù)雜度：O(n)
穩(wěn)定性：穩(wěn)定
代碼
void mergeSort(int [] array){
mergeSort(array,0,array.length-1);
}
void mergeSort(int[] array, int left, int right) {
if(left>=right) return;
int mid = (left+right)>>1;
//左邊排序
mergeSort(array,left,mid);
//右邊排序
mergeSort(array,mid+1,right);
//歸并
mergeSort(array,left,mid,right);
}
void mergeSort(int[] array, int left, int mid, int right) {
int [] temp = new int[right+1];
for(int i=left;i<=right;i++){
temp[i]=array[i];
}
int rig = mid + 1;
for(int i = left ;i <= right;i++){
//左邊拿完了拿右邊
if(left > mid ) array[i] = temp[rig++];
//右邊完了拿左邊
else if(rig>right) array[i] = temp[left++];
//2邊都有做比較
else if(temp[left]>temp[rig]) array[i] = temp[rig++];
else array[i]=temp[left++];
}
}
```0