排序

2021-01-15

排序算法集合

十大排序算法

Imgur

快排

递归实现

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        quickSort(arr, 0, arr.length - 1);
        return Arrays.copyOf(arr, k);
    }
    private void quickSort(int[] arr, int l, int r) {
        // 子数组长度为 1 时终止递归
        if (l >= r) return;
        // 哨兵划分操作（以 arr[l] 作为基准数）
        int i = l, j = r;
        while (i < j) {
            // 右边的大于哨兵，不需要交换
            while (i < j && arr[j] >= arr[l]) j--;
            // 左边的小于哨兵，也不需要交换
            while (i < j && arr[i] <= arr[l]) i++;
            // 找到需要交换的值，进行交换
            swap(arr, i, j);
        }
        // 将哨兵交换到分界位置
        swap(arr, i, l);
        // 递归左（右）子数组执行哨兵划分
        quickSort(arr, l, i - 1);
        quickSort(arr, i + 1, r);
    }
    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

作者：jyd
链接：https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/solution/jian-zhi-offer-40-zui-xiao-de-k-ge-shu-j-9yze/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

非递归实现

class Solution{
        public void quickSort(int[] a, int start, int end) {
        LinkedList<Integer> stack = new LinkedList<Integer>(); // 用栈模拟
        if (start < end) {
            // 将当前的右边界入栈
            stack.push(end);
            // 将当前的左边界入栈
            stack.push(start);
            // 如果栈不为空,说明还有待排序的区间
            while (!stack.isEmpty()) {
                // 后入栈的先出,第一个出栈的是左边界
                int l = stack.pop();
                // 后入栈的先出,第二个出栈的是右边界
                int r = stack.pop();
                // 内部划分完后的index
                int index = partition(a, l, r);
                // 如果当前的左边界小于index,说明左边还没有完成排序
                if (l < index - 1) {
                    // 当前的index-1是右边界
                    stack.push(index - 1);
                    // 当前的左边界还是下一次划分的左边界
                    stack.push(l);
                }
                // 如果当前的右边界大于index,说明右边还没有完成排序
                if (r > index + 1) {
                    // 当前的右边界是下一次划分的右边界
                    stack.push(r);
                    // 当前的左边界是index+1
                    stack.push(index + 1);
                }
            }
        }
    }

    // 划分数组，真正的排序逻辑
    private int partition(int[] a, int l, int r) {
        // 选取开头的那个作为哨兵
        int pivot = a[l];
        int i = l, j = r;
        while (i < j) {
            // 右边的大于哨兵不需要交换
            while (i < j && a[j] >= pivot) j--;
            // 坐标的小于哨兵不需要交换
            while (i < j && a[i] <= pivot) i++;
            // 找到需要交换的值，进行交换
            swap(a, i, j);
        }
        // 将哨兵交换到分界位置
        swap(a, i, l);
        return i;
    }

    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

快排应用

快速排序修改版

插入排序

对链表进行插入排序

冒泡排序

基数排序

基数排序
应用
最大间距

归并排序

算法步骤

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
设定两个指针，最初位置分别为两个已经排序序列的起始位置；
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
重复步骤 3 直到某一指针达到序列尾；

将另一序列剩下的所有元素直接复制到合并序列尾。

源代码


class Solution {
    int[] tmp;

    public int[] sortArray(int[] nums) {
        tmp = new int[nums.length];
        mergeSort(nums, 0, nums.length - 1);
        return nums;
    }

    public void mergeSort(int[] nums, int l, int r) {
        if (l >= r) return;
        int m = (l + r) >> 1;
        mergeSort(nums, l, m);
        mergeSort(nums, m + 1, r);
        int i = l, j = m + 1;
        int cnt = 0;
        // 合并两个有序数组
        while (i <= m && j <= r) {
            if (nums[i] < nums[j]) {
                tmp[cnt++] = nums[i++];
            }else {
                tmp[cnt++] = nums[j++];
            }
        }
        // 左边没用完
        while (i <= m) tmp[cnt++] = nums[i++];
        // 右边没用完
        while (j <= r) tmp[cnt++] = nums[j++];
        // 放到原来的数组中
        for (int k = 0; k < r - l + 1; ++k) {
            nums[k + l] = tmp[k];
        }
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/sort-an-array/solution/pai-xu-shu-zu-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

排序链表

桶排序

堆排序

大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

算法步骤

创建一个堆 $H[0……n-1]$；
把堆首（最大值）和堆尾互换；
把堆的尺寸缩小 1，并调用 maxHeapify(0)，目的是把新的数组顶端数据调整到相应位置；

重复步骤 2，直到堆的尺寸为 1。

代码实现

class Solution {
    public void heapSort(int[] nums) {
        int heapSize = nums.length;
        // 建最大堆在这里进行
        buildMaxHeap(nums, heapSize);
        // 排序在这里进行
        for (int i = heapSize - 1; i > 0; i--) {
            swap(nums, 0, i);
            heapSize--;
            maxHeapify(nums, 0, heapSize);
        }
    }

    // 建大根堆
    public void buildMaxHeap(int[] nums, int heapSize) {
        for (int i = heapSize / 2; i >= 0; i--) {
            maxHeapify(nums, i, heapSize);
        }
    }

    public void maxHeapify(int[] nums, int index, int headSize) {
        // l代表左子树的元素，r代表右子树的元素，largest是当前的根节点元素的index
        int l = index * 2 + 1, r = index * 2 + 2, largest = index;
        // 如果左子树的节点大于当前的最大值，最大的是左子树的根节点的index对应的值
        if (l < headSize && nums[l] > nums[largest]) largest = l;
        // 如果右子树的节点大于当前的最大值，最大的是右子树的根节点的index对应的值
        if (r < headSize && nums[r] > nums[largest]) largest = r;
        // 如果最大的不是根节点的值，需要交换最大值与根节点的值，从最大值的index继续heapify
        if (largest != index) {
            swap(nums, index, largest);
            maxHeapify(nums, largest, headSize);
        }
    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

堆排序的应用

找最大的k个数

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int heapSize = nums.length;
        // 建立最大堆已经完成
        buildMaxHeap(nums, heapSize);

        // 堆排序
        for (int i = nums.length - 1; i >= nums.length - k + 1; --i) {
            swap(nums, 0, i);
            --heapSize;
            maxHeapify(nums, 0, heapSize);
        }
        return nums[0];
    }
    // 建立堆
    public void buildMaxHeap(int[] a, int heapSize) {
        for (int i = heapSize / 2; i >= 0; --i) {
            maxHeapify(a, i, heapSize);
        } 
    }
    // 大根堆调整
    public void maxHeapify(int[] a, int i, int heapSize) {
        int l = i * 2 + 1, r = i * 2 + 2, largest = i;
        if (l < heapSize && a[l] > a[largest]) {
            largest = l;
        } 
        if (r < heapSize && a[r] > a[largest]) {
            largest = r;
        }
        if (largest != i) {
            swap(a, i, largest);
            maxHeapify(a, largest, heapSize);
        }
    }

    public void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array/solution/shu-zu-zhong-de-di-kge-zui-da-yuan-su-by-leetcode-/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

插入排序

package runoob;

/**
 * 插入排序
 */
public class InsertionSort {
    //核心代码---开始
    public static void sort(Comparable[] arr){

        int n = arr.length;
        for (int i = 0; i < n; i++) {
            // 寻找元素 arr[i] 合适的插入位置
           for( int j = i ; j > 0 ; j -- )
                if( arr[j].compareTo( arr[j-1] ) < 0 )
                    swap( arr, j , j-1 );
                else
                    break;
        }
    }
    //核心代码---结束
    private static void swap(Object[] arr, int i, int j) {
        Object t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    public static void main(String[] args) {

        int N = 20000;
        Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
        InsertionSort.sort(arr);
        for( int i = 0 ; i < arr.length ; i ++ ){
            System.out.print(arr[i]);
            System.out.print(' ');
        }
    }

}