8大排序算法---我熟知3（归并排序/快速排序/堆排序）

排序算法：

快排： o(nlogn) o(1)不稳定

归并：o(nlogn) o(n) 稳定

基数：

冒泡

睡眠

面条

烙饼

1、quicksort:

• 返回条件：start >=end
• private = a[start]+a[end]/2
• while(left <= right)
• 　　while(left <= right && a[left] < privot)
• 　　while(left <= right && a[right] > privot)

public class Solution {
    /**
     * @param A an integer array
     * @return void
     */
    public void sortIntegers2(int[] A) {
        quickSort(A, 0, A.length - 1);
    }
    
    private void quickSort(int[] A, int start, int end) {
        if (start >= end) {
            return;
        }
        
        int left = start, right = end;
        // key point 1: pivot is the value, not the index
        int pivot = A[(start + end) / 2];

        // key point 2: every time you compare left & right, it should be 
        // left <= right not left < right
        while (left <= right) {
            // key point 3: A[left] < pivot not A[left] <= pivot
            while (left <= right && A[left] < pivot) {
                left++;
            }
            // key point 3: A[right] > pivot not A[right] >= pivot
            while (left <= right && A[right] > pivot) {
                right--;
            }
            if (left <= right) {
                int temp = A[left];
                A[left] = A[right];
                A[right] = temp;
                
                left++;
                right--;
            }
        }
        
        quickSort(A, start, right);
        quickSort(A, left, end);
    }
}

快排的优化有两点：

1.取基准时尽量随机，使得每次分割尽量平均，特别是预防有序的数据。------解决三数取中当基准

2.对于重复的元素，要聚合相同的元素，特别是对于有重复的元素时候（碰到连续相等情况会被不均分）。所以比较时候是<和>  -----两路排或者三路排

3.当待排元素长度分割到一定小时采用插入排序，比快排效果好。

https://blog.csdn.net/u012104219/article/details/80873484

https://blog.csdn.net/k_koris/article/details/80585979

https://www.cnblogs.com/c4isr/p/4603980.html

所以最好的优化是： 三数取中+聚合相同元素+插排

int Median(int[] a, int left, int right){
  int midIndex = (left + right) >>1;
  if(a[left] > a[midIndex]){
    swap(a[left],a[midIndex]);
    }
   if(a[left] > a[right]){
      swap(a[left],a[right]);
    } 
   if(a[midIndex] > a[right]){
      swap(a[midIndex],a[right]);
    } 
   swap(a[midIndex],a[right - 1]);
   return a [right - 1] ;//这里取right -1 为基准点                  
}

 竟然还有双基准点

 http://www.importnew.com/8445.html

2、mergesort :分治的思想 o(n) : 合并两个数组

主函数：异常检查

　　　　创建新数组

mergesort（int[] temp, int start ,int end,int[] A）

　　返回条件：start > end {return}

　　左排；

　　右排;

　　merge()

merge(int[] temp, int start, int end, int[] A) {

// merge two sorted subarrays in A to temp array

　　while(left <= mid && right <= end) {

　　　　if A[start] < A[end] {temp[index++] = A[start++]}

　　　　else :

　　有一个剩余,左边，右边剩余

　　while(left <= mid) : temp[index++] = A[left++]

// copy temp back to A

　　for循环赋值回A　　

}　　

public class Solution {
    /**
     * @param A an integer array
     * @return void
     */
    public void sortIntegers2(int[] A) {
        // use a shared temp array, the extra memory is O(n) at least
        int[] temp = new int[A.length];
        mergeSort(A, 0, A.length - 1, temp);
    }
    
    private void mergeSort(int[] A, int start, int end, int[] temp) {
        if (start >= end) {
            return;
        }
        
        int left = start, right = end;
        int mid = (start + end) / 2;

        mergeSort(A, start, mid, temp);
        mergeSort(A, mid+1, end, temp);
        merge(A, start, mid, end, temp);
    }
    
    private void merge(int[] A, int start, int mid, int end, int[] temp) {
        int left = start;
        int right = mid+1;
        int index = start;
        
        // merge two sorted subarrays in A to temp array
        while (left <= mid && right <= end) {
            if (A[left] < A[right]) {
                temp[index++] = A[left++];
            } else {
                temp[index++] = A[right++];
            }
        }
        while (left <= mid) {
            temp[index++] = A[left++];
        }
        while (right <= end) {
            temp[index++] = A[right++];
        }
        
        // copy temp back to A
        for (index = start; index <= end; index++) {
            A[index] = temp[index];
        }
    }
}

 3、堆排序

重新理解堆排序：
堆排序步骤：
1）生成小根堆（大根堆）
先按照数组排（R[0...n-1]下标）序生成完全二叉树，然后从最后一个非叶子节点（n/2 - 1）开始，把其当做是根节点，逐步向前调整（根节点是最小的），进行创建小根堆。
2）堆调整：
1. 取出小跟堆的顶点值，将其与堆中第N(N=n)个节点互换位置，即R[N-1]。
2. 此时小根堆被破坏，形成将得到新的无序区(R1,R2,......Rn-1)和新的有序区(Rn),且满足R[1,2...n-1]>=R[n];由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,......Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2....Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
最小堆排序后生成：逆序即：从大到小的排序
代码：
//生成小根堆
/**
* 调整成最小堆
* @param arr 数组
* @param top 堆顶位置
* @param tail 堆未位置
*/
public static void fitToMinHeap(int[] arr, int top, int tail) {
int i = top;
int temp = arr[i];
int j = 2 * i + 1;//找到子节点
while (j < tail) {
if (j + 1 < tail && arr[j + 1] < arr[j])//找出左右子节点中的最小
j++;
if (arr[j] >= temp)//子节点都大于父节点则跳出
break;
arr[i] = arr[j];//将子节点向上移,即移到父节点
i = j;
j = 2 * i + 1;
}
arr[i] = temp;
}
//堆排序
public static void heapSort(int[] arr) {
int n = arr.length;
for (int j = n / 2 - 1; j >= 0; j--)//从最后一个非叶子节点开始,初始化生成数组表示的最小堆
fitToMinHeap(arr, j, n);
for (int i = n - 1; i > 0; i--) {//每次拿出堆的顶点值
//把堆中的顶点与a[i]点互换
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
fitToMinHeap(arr, 0, i);//交换后再对前i个节点进行最小堆化
}
}