排序算法

数据结构与算法

一、结论

二、直接插入排序

思想：将第一个记录看成有序的，右边都是未排序的部分，从未排序的部分依次选择一个记录插入到左边有序部分合适的位置。

public void insertSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int cur = arr[i];
        int j = i - 1;
        for (; j >= 0; j--) {
            if (cur > arr[j]) {
                break;
            }
            // 移动元素
            arr[j+1] = arr[j];
        }
        // 插入元素
        arr[j+1] = cur;
    }
}

特点：每一趟都需要移动元素
优化思路：直接插入排序采用遍历的方式在有序部分寻找插入位置，这个部分可以转换为二分查找，这就是二分查找的插入排序

插入排序在数组已经基本有序的情况下性能比较好。

三、希尔排序

我们知道插入排序在原序列已经基本有序的情况下性能是比较好的，那怎么才能让一个数组基本有序呢？这就是希尔排序，可以认为希尔排序就是插入排序的一种特殊的优化方式。

思路：先将整个待排序的的记录按照一定的步长分割为若干子序列，对子序列分别做直接插入排序，子序列排序完成之后，整个序列也基本有序了，再对全体记录进行一次直接插入排序。

public void sort(int[] arr) {
    int length = arr.length;
    // 步长
    int gap = 1;
    while (gap < length) {
        gap = gap * 3 + 1;
    }
    while (gap > 0) {
        for (int i = gap; i < length; i++) {
            int tmp = arr[i];
            int j = i - gap;
            // 跨步长排序
            while (j >= 0 && arr[j] > tmp) {
                arr[j + gap] = arr[j];
                j -= gap;
            }
            arr[j + gap] = tmp;
        }
        gap = gap / 3;
    }
}

希尔排序的时间复杂度与步长选择有关，最优步长没有答案。

四、快速排序

快速排序的核心思想是分治法。它的实现方式是每次从序列中选出一个基准值，其他数依次和基准值做比较，比基准值大的放右边，比基准值小的放左边，然后递归处理左右两部分序列，直到最后都变成单个元素，整个数组就成了有序的序列。

// 单边扫描
public void sort(int[] arr) {
    sort(arr, 0, arr.length - 1);
}
private void sort(int[] arr, int startIndex, int endIndex) {
    if (endIndex <= startIndex) {
        return;
    }
    // 切分
    int pivotIndex = partitionV2(arr, startIndex, endIndex);
    sort(arr, startIndex, pivotIndex - 1);
    sort(arr, pivotIndex + 1, endIndex);
}
private int partitionV2(int[] arr, int startIndex, int endIndex) {
    int pivot = arr[startIndex]; // 取基准值
    int mark = startIndex; // Mark初始化为起始下标
    for (int i = startIndex + 1; i <= endIndex; i++) {
        if (arr[i] < pivot) {
            // 小于基准值 则mark+1，并交换位置。
            mark++;
            int p = arr[mark];
            arr[mark] = arr[i];
            arr[i] = p;
        }
    }
    // 基准值与mark对应元素调换位置
    arr[startIndex] = arr[mark];
    arr[mark] = pivot;
    return mark;
}

双边扫描：

public void sort(int[] arr) {
    sort(arr, 0, arr.length - 1);
}
public void sort(int[] arr, int low, int high) {
    if (low >= high) {
        return;
    }
    int med = partitionV2(arr, low, high);
    sort(arr, low, med - 1);
    sort(arr, med + 1, high);
}
public static int partitionV2(int[] arr, int low, int high) {
    int pivot = arr[low];
    while (low < high) {
        while(low < high && arr[high] > pivot) {
            high--;
        }
        arr[low] = arr[high];
        while(low < high && arr[low] <= pivot) {
            low++;
        }
        arr[high] = arr[low];
    }
    arr[low] = pivot;
    return low;
}

如果每次递归选择的基准点都正好可以将序列等分成两部分将能达到最好的效率，相反如果每一次递归选择的基准点刚好是序列的最大值或者最小值，那将达到最差的效率。
可以看到快速排序的效率是与基准点的选择有关的。一般有如下几种选取基准点的方式：

• 固定位置：总是选取第一个或者最后一个元素作为基准点
• 随机选取：随机选取一个元素作为基准点，由于位置是随机的，那么产生的分割也不会总是出现劣质的分割
• 三数取中：选取序列中low、mid、high三个位置上的数据进行排序，取中间的那个数作为基准。实际上是通过采样数据估计中值的方式，但是并准确。

其它优化方式：

• 当递归进行到一定程度之后，认为整个序列已经基本有序了，这个时候退出递归，使用简单插入排序来完成剩下的排序过程。
• 如果序列中有重复的元素，可以在每一趟递归的时候把和基准点相同的元素聚在一起，找到边界，之后递归的过程中，这些相同的元素不再参与，这就是三路划分快速排序。

五、堆排序

堆排序是利用堆结构来完成的排序，堆有大根堆和小根堆两种，大根堆的根节点总是大于左右子节点，左右子树也是大根堆；小根堆相反。
堆排序的过程就是将元素全部入堆，根据堆的定义，每次从堆顶取出一个元素，当全部取完之后，序列也就是有序的了。

java中PriorityQueue就是堆，可以利用PriorityQueue来完成排序。

public void sort(int[] arr) {
    PriorityQueue<Integer> queue = new PriorityQueue<>();
    for(int n : arr) {
        queue.add(n);
    }
    int i = 0;
    while (!queue.isEmpty()) {
        Integer n = queue.poll();
        arr[i++] = n;
    }
}

当然也可以自己实现堆：

public static void sort(int[] arr) {
    int length = arr.length;
    //构建堆
    buildHeap(arr， length);
    for ( int i = length - 1; i > 0; i-- ) {
        //将堆顶元素与末位元素调换
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        //数组长度-1 隐藏堆尾元素
        length--;
        //将堆顶元素下沉 目的是将最大的元素浮到堆顶来
        sink(arr， 0， length);
    }
}
private static void buildHeap(int[] arr， int length) {
    for (int i = length / 2; i >= 0; i--) {
        sink(arr， i， length);
    }
}
private static void sink(int[] arr， int index， int length) {
    int leftChild = 2 * index + 1;//左子节点下标
    int rightChild = 2 * index + 2;//右子节点下标
    int present = index;//要调整的节点下标
    //下沉左边
    if (leftChild < length && arr[leftChild] > arr[present]) {
        present = leftChild;
    }
    //下沉右边
    if (rightChild < length && arr[rightChild] > arr[present]) {
        present = rightChild;
    }
    //如果下标不相等 证明调换过了
    if (present != index) {
        //交换值
        int temp = arr[index];
        arr[index] = arr[present];
        arr[present] = temp;
        //继续下沉
        sink(arr， present， length);
    }
}

六、归并排序

归并排序的核心思想是分治，先将整个序列划分为几个部分，将子序列分别排序，然后让子序列段间有序，直到最后合并成一个完整的序列。

public static void sort(int[] arr) {
    int[] tempArr = new int[arr.length];
    sort(arr, tempArr, 0, arr.length - 1);
}
private static void sort(int[] arr, int[] tempArr, int startIndex, int endIndex) {
    if (endIndex <= startIndex) {
        return;
    }
    //中部下标
    int middleIndex = startIndex + (endIndex - startIndex) / 2;
    //分解
    sort(arr, tempArr, startIndex, middleIndex);
    sort(arr, tempArr, middleIndex + 1, endIndex);
    //归并
    merge(arr, tempArr, startIndex, middleIndex, endIndex);
}
private static void merge(int[] arr, int[] tempArr, int startIndex, int middleIndex, int endIndex) {
    //复制要合并的数据
    for (int s = startIndex; s <= endIndex; s++) {
        tempArr[s] = arr[s];
    }
    int left = startIndex;//左边首位下标
    int right = middleIndex + 1;//右边首位下标
    for (int k = startIndex; k <= endIndex; k++) {
        if (left > middleIndex) {
            //如果左边的首位下标大于中部下标,证明左边的数据已经排完了。
            arr[k] = tempArr[right++];
        } else if (right > endIndex) {
            //如果右边的首位下标大于了数组长度,证明右边的数据已经排完了。
            arr[k] = tempArr[left++];
        } else if (tempArr[right] < tempArr[left]) {
            arr[k] = tempArr[right++];//将右边的首位排入,然后右边的下标指针+1。
        } else {
            arr[k] = tempArr[left++];//将左边的首位排入,然后左边的下标指针+1。
        }
    }
}