排序是我們接觸數學以後就一直圍繞我們的問題，國小數學課上有給數字排序，在生活中，給長輩們排序，在coding的世界中，也離不開排序，而在程式人生中，我們接觸最早的排序就屬于冒泡排序了。下面我就來在coding的世界中淺聊排序。
排序從總體來說分為内部排序和外部排序。
其中内部排序一般使用計算機記憶體進行排序（記憶體：又稱記憶體儲器，它是與CPU進行溝通的橋梁。計算機中所有程式的運作都是在記憶體中進行的，是以記憶體的性能對計算機的影響非常大。記憶體(Memory)也被稱為記憶體儲器，其作用是用于暫時存放CPU中的運算資料，以及與硬碟等外部存儲器交換的資料。隻要計算機在運作中，CPU就會把需要運算的資料調到記憶體中進行運算，當運算完成後CPU再将結果傳送出來，記憶體的運作也決定了計算機的穩定運作。 記憶體是由記憶體晶片、電路闆、金手指等部分組成的）。
其中外部排序一般是記憶體和外存結合使用。外部排序指的是大檔案的排序，即待排序的記錄存儲在外存儲器上，待排序的檔案無法一次裝入記憶體，需要在記憶體和外部存儲器之間進行多次資料交換，以達到排序整個檔案的目的。
内部排序有：插入排序(直接插入排序、希爾排序)；選擇排序（簡單選擇排序、堆排序）；交換排序（冒泡排序、快速排序）；歸并排序；基數排序。
外部排序有：外部快排，多路歸并排序等等，一般研究較多的是内部排序。是以這篇部落格會有重點性的介紹内部的排序。又簡稱内部排序大亂鬥，即窩裡鬥。
下面的兩張圖檔詳細的劃分了排序分為内、外排序，内部排序都有哪些排序，外部排序又有哪些。其中内部排序又列出了時間複雜度，最壞時間複雜度，空間複雜度。穩定性等。下面你先仔細閱讀這兩張圖檔，接下來會詳細說說内部排序大亂鬥，又稱窩裡鬥。
圖一：排序分類圖
圖二：排序穩定性、複雜度圖
=====================================================================
冒泡排序：
冒泡排序算法的起名貼切于算法本身的名字，即每周遊循環一次，都會把無序中的最大數放到最後，就像水中的氣泡一樣，在水底時最小，越往上升就越大，冒泡排序也類似于這樣的過程，故稱為冒泡排序。
概念：該算法就是重複地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重複地進行直到沒有再需要交換，也就是說該數列已經排序完成。
算法原理：
1：比較相鄰的元素，如果第一個比第二個大，就交換它們兩個。
2：對每一對相鄰元素作同樣的工作，從開始第一對到結尾最後一對。在這一點，最後的元素應該會是最大的數。
3：針對所有的元素重複以上的步驟，出了最後一個。
4：持續每次對越來越少的元素重複上面的步驟，直到沒有任何一對數字需要比較。
算法複雜度：
冒泡排序：時間複雜度O(n^2)；最壞的時間複雜度O(n^2)；空間複雜度：O(1)；穩定性：穩定；
Coding：
void bubbleSort(int []a){
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：在初始時,n個無序序列，a[0]自己形成一個有序區，a[1,.....n-1]為無序區。令i=1；
2：将a[i]并入目前的有序區a[0,...,i-1]中形成a[0, ..., i]的有序區間。
3：i++并重複第2步直到i==n-1。排序完成。
算法複雜度：
直接插入排序：時間複雜度：O(n^2)；最壞時間複雜度：O(n^2)；空間複雜度：O(1)；
Coding1：
void straightInsertSort(int []a){
for(int i = 1; i < a.length; i++){
if(a[i] < a[i-1]){
int temp = a[i];
int k = i-1;
for(int j = k; j >=0 && a[j] > temp; j--){
a[j+1] = a[j];
k--;
}
a[k+1] = temp;
}
}
}
Coding2：
public void directlyArray(int []arrs){
for(int i = 1; i < arrs.length; i++){
int ins = arrs[i];
int j = 0;
for(j = i; j > 0 && arrs[j-1] > ins; j--){
arrs[j] = arrs[j-1];
}
arrs[j] = ins;
}
}
=====================================================================
簡單選擇排序：
簡單選擇排序我覺得關鍵字在選擇，就是每次都在無序的元素中找到其中最小的一個元素。
概念：掃描所有的元素，得到最小的元素，并将最小的元素與左邊第一個元素進行交換。再次掃描除第一位置的所有元素，得到最小的元素，與左邊第二個元素進行交換。以此類推。
算法原理：
即通過n-i次元素的比較，從n-i+1個記錄中選出最小的元素，并和第i個元素進行交換位置。
算法複雜度：
簡單選擇排序：時間複雜度：O(n^2)；最壞時間複雜度：O(n^2)；空間複雜度：O(1)；
Coding：
//選擇排序
public void selectArray(int arrs[]){
for(int i = 0; i < arrs.length-1; i++){
int min = i;
for(int j = i+1; j < arrs.length; j++){
if(arrs[j] < arrs[min]){
min = j;
}
}
int temp = arrs[min];
arrs[min] = arrs[i];
arrs[i] = temp;
}
}
=====================================================================
歸并排序：
歸并排序概括為一句話就是采用了經典的分治政策。分開，治（2路合并排序）
概念：歸并排序（Merging Sort）就是利用歸并的思想實作的排序方法。它的原理是假設初始序列含有n個記錄，則可以看成是n個有序的子序列，每個子序列的長度為1，然後兩兩歸并，得到n/2取上整數個長度為2或1的有序子序列；再兩兩歸并，......，如此重複，直至得到一個長度為n的有序序列為止，這種排序方法稱為2路歸并排序。
算法原理：
把原始無序數組成2路分開，再在每次子數組序列成2路分開，知道形成了每個元素成為一個子數組，然後再形成2路合并，每次合并都是有序的合并。這就是我認為的歸并排序原理。
時間複雜度：
歸并排序：時間複雜度為：O（nlogn）（最壞最好的時間複雜度都為它）；空間複雜度：O（n）；穩定的排序算法。
圖解：
Coding：
/**
* 歸并排序
* @author Peter
*
*/
public class Main {
//分
public int[] sort(int arrays[], int low, int high){
int mid = (low + high) / 2;
if(low < high){
// 左邊
sort(arrays, low, mid);
// 右邊
sort(arrays, mid + 1, high);
// 左右歸并
merge(arrays, low, mid, high);
}
return arrays;
}
//治
public static void merge(int []arrays, int low, int mid,int high){
int temp[] = new int[high - low + 1];
int i = low; //左指針
int j = mid + 1; //右指針
int k = 0;
//把較小的數先移到新數組
while(i <= mid && j <= high){
if(arrays[i] < arrays[j]){
temp[k++] = arrays[i++];
}else{
temp[k++] = arrays[j++];
}
}
//把左邊剩餘的移入新數組
while(i <= mid){
temp[k++] = arrays[i++];
}
//把右邊剩餘的移入新數組
while(j <= high){
temp[k++] = arrays[j++];
}
//新數組中的數覆寫arrays數組
for (int k2 = 0; k2 < temp.length; k2++) {
arrays[k2+low] = temp[k2];
}
}
//測試
public static void main(String[] args) {
int[] nums = { 12, 17, 18, 13, 11, 16, 19, 10, 15, 14 };
Main m1 = new Main();
m1.sort(nums, 0, nums.length-1);
System.out.println(Arrays.toString(nums));
}
}
=====================================================================
快速排序：
快速排序一句話概括為大而化小，小而化無，每次都分成兩部分，其中一部分的最大元素小于另一部的最小元素。
算法原理：
通過一趟排序将待排記錄分割成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分記錄的關鍵字小，則可分别對這兩部分記錄繼續進行排序，以達到整個序列有序的目的。
時間複雜度分析：
快速排序：平均時間複雜度為O（nlogn）；最壞的時間複雜度為O（n^2）；最優的時間複雜度為O（nlogn）;
平均空間複雜度為O（logn）；最壞的空間複雜度為O（n）；最優的空間複雜度為O（logn）。
public void quickSort(int []nums){
qSort(nums, 0, nums.length-1);
}
private void qSort(int[] nums, int low, int high) {
int pivot;
if(low < high){
pivot = partition(nums, low, high); //算出樞軸值
qSort(nums, low, pivot - 1); //對低子表遞歸排序
qSort(nums, pivot + 1, high); //對高子表遞歸排序
}
}
private int partition(int[] nums, int low, int high) {
int pivotkey;
pivotkey = nums[low]; //用子表的第一個記錄作為樞軸記錄
while(low < high){ //從表的兩端交替向中間掃描
while(low < high && nums[high] >= pivotkey){ //從數組後面向前掃描，将比pivotkey值小的交換到低端
--high;
}
swap(nums, low, high);
while(low < high && nums[low] <= pivotkey){ //從數組前面向後掃描，将比pivotkey值大的交換到高端
++low;
}
swap(nums, low, high);
}
return low;
}
//數組交換值
private void swap(int[] nums, int low, int high) {
int temp = nums[low]; //比pivotkey小的值交換到低端
nums[low] = nums[high];
nums[high] = temp;
}
public static void main(String[] args) { //測試
Main m = new Main();
int nums[] = {50, 10, 90, 30, 70, 40, 80, 60, 20};
m.quickSort(nums);
for(int i : nums){
System.out.println(i);
}
}
優化快速排序：
1：在partition( )中優化選取樞軸pivotkey
2：在partition( )中優化不必要的交換
注：優化不必要的交換，就必須是數組中有一個元素的位置為備援的，這裡選取第一個位置
void quickSort(int nums[]){
qSort(nums, 1, nums.length-1);
}
private void qSort(int[] nums, int low, int high) {
int pivot;
if(low <high){
pivot = partition(nums, low, high); //算出樞軸值
qSort(nums, low, pivot - 1); //對低子表遞歸排序
qSort(nums, pivot + 1, high); //對高子表遞歸排序
}
}
private int partition(int[] nums, int low, int high) {
int middle = low + (high - low) / 2; //數組中間的元素的下标
if(nums[low] > nums[high]){ //交換左端與右端資料，保證左端較小
swap(nums, low, high);
}
if(nums[middle] > nums[high]){ //交換中間和右端資料，保證中間較小
swap(nums, middle, high);
}
if(nums[middle] > nums[low]){ //交換左端與中間資料，保證左端為左、中、右端的次小元素
swap(nums, middle, low);
}
int pivotkey = nums[low];
nums[0] = pivotkey;
while(low < high){
while(low < high && nums[high] >= pivotkey){
--high;
}
nums[low] = nums[high];
while(low < high && nums[low] <= pivotkey){
++low;
}
nums[high] = nums[low];
}
nums[low] = nums[0];
return low;
}
//交換數組中的兩個值
private void swap(int[] nums, int low, int high) {
int temp = nums[low];
nums[low] = nums[high];
nums[high] = temp;
}
public static void main(String[] args) { //測試
Main1 m1 = new Main1();
int nums[] = {0, 10, 90, 30, 70, 40, 80, 60, 20};
m1.quickSort(nums);
for (int i = 1; i < nums.length; i++) {
System.out.println(nums[i]);
}
}
3：優化小數組的排序方案，在qSort方法中規定（high - low）小于某一值時用小數組排序方式（直接插入排序）。
if((high - low) > MaxLen){
pivot = partition(nums, low, high); //算出樞軸值
qSort(nums, low, pivot - 1); //對低子表遞歸排序
qSort(nums, pivot + 1, high); //對高子表遞歸排序
}else{
//直接插入排序
}
4：優化遞歸操作。對于高子表遞歸進行優化。減少耗費的空間。
if((high - low) > MaxLen){
while(low < high){
pivot = partition(nums, low, high); //算出樞軸值
qSort(nums, low, pivot - 1); //對低子表遞歸排序
low = pivot + 1; //尾遞歸
}
}else{
//直接插入排序
}
堆排序：時間複雜度O（nlogn）；不穩定的排序算法
//堆排序
public class HeapSort {
//數組交換
public static void swap(int nums[], int i, int j){
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
//堆排序先建立大根堆或者小根堆，再進行排序
public static void heapSort(int []arr){
if(arr == null || arr.length < 2){
return;
}
for(int i = 0; i < arr.length; i++){
heapInsert(arr, i);//調整為大根堆,從下往上調
}
int size = arr.length;
swap(arr, 0, --size);//把root和最後一個交換
while(size > 0){
//重新調整為大根堆
heapify(arr, 0, size);
swap(arr, 0, --size);//根結點最大,是以減掉
}
}
//重新調整為大根堆,從上往下調
private static void heapify(int[] arr, int i, int size) {
int left = 2 * i + 1; //取最小的左結點
while(left < size){//保證數組不越界
//取得最大孩子結點的下标
int largest = left+1<size &&arr[left+1]>arr[left]?left+1:left;
//比較最大孩子結點和父結點的值
largest = arr[largest]>arr[i]?largest:i;
if(largest==i){
break;//如果最大下标是父結點,則不要交換,跳出while循環
}
//否則需要交換
swap(arr, i, largest);
i = largest;
left = 2*i+1;
}
}
//調整大根堆,不斷向上循環,調整大根堆
private static void heapInsert(int[] arr, int i) {
while(arr[i] > arr[i-1]/2){//循環結束,調整為大根堆
swap(arr, i, (i-1)/2);
i = (i-1)/2;
}
}
}