常见排序算法 (一)

背景

由于算法知识的极度缺乏，但是做程序猿，算法其实是进阶绕不过去的坎，因此硬着头皮从各种排序算法学起了，感觉有些收获，而且当你理解了算法的原理后，能帮你去分析复杂的数据结构，也能帮你去手写代码。

常见排序算法

快速排序算法

原理：分治，前后两个指针交替前进，然后递归，主要步骤是：

取一个数作为基数（一般就选第一个）
将数组中比这个数大的放在它的右边，比基数小的放在它左边
递归两遍的数组

public void quickSort(int[] a,int low,int high){
    int i = low;
    int j = high;
    int temp = a[low] //比较的数
    
    while(i < j){
        while(i<j && a[j] >= temp){
            j--;
        }
        if(i < j) {
            a[i] = a[j];
            i++;
        }
        
        while(i < j && a[j] < temp){
            i++;
        }
        if(i<j){
            a[j] = a[i];
            j--;
        }
    }
    
    a[i] = temp;
    quickSort(a,low,i-1);
    quickSort(a,i+1;high);
}

堆排序

原理：堆其实是一个完全二叉树，它的特征是当前结点下标为i，那么它的根结点为i/2，它的左子结点为：2i+1；右子结点为：2i+2。
堆排序要经过两步：

将树变为稳定的二叉树（大堆模式），即每个根结点都要大于等于它的子结点。
将根结点和最后一个结点互换，递归以上操作

手写代码：

//第一步变为稳定树
public void adjustHeap(int[] ,int parent,int length){
    int temp = a[parent];
    int leftChildIndex = 2*parent + 1;
    
    while(leftChildIndex < length){
        if (a[leftChildeIndex] < a[leftChildIndex + 1]{
            leftChildIndxe = leftChildIndex + 1;
        }
        
        if (temp > a[leftChildIndex]){
            break;
        }
        
        a[parent] = a[leftChildIndex];
        
        parent = leftChildIndex;
        leftChildIndex = 2*leftChildIndex + 1;
    }
    
    a[parent] = temp;
}

冒泡排序

原理：内存循环会不停比较两个数的大小，进行换位，完成一轮后，最大的数会排在最后。（注意和选择排序的区别，选择排序是内层循环和外层循环比较）
算法时间复杂度：O（n2）

public static void bubbleSort(int[] a){

    int len = a.length;
    for(int i =0 ;i<len;i++){
        for(int j=1;j<len - i -1;j++){//每一轮最后一个数不用比较
        // 内存循环比较相邻两个数
            if(a[j] > a[j+1]){
                int temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp;
            }
        }
    }
}

选择排序

原理：遍历数组中最小值，放在最左边，再从剩下数组中找最小值，直到排序完成（在要排序的一组数中，选出最小的一个数与第一个位置的数交换位置）
算法时间复杂度：O（n2）


public static void selectSort(int[] a){
    int len = a.length;
    for(int i = 0;i<len;i++){
        for(int j = i+1; j< len;j++){
        // 和外层第一个元素比较
            if(a[j] > a[i]){
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }
    }

}