排序算法

Created at 2019-09-10 Updated at 2020-07-29 Category 算法 Tag 排序 views

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i] = r[j]，且 r[i] 在 r[j] 之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

• 稳定：如果 a 原本在 b 前面，而 a = b，排序后 a 仍然在 b 前面。
• 不稳定： 如果 a 原本在 b 前面，而 a = b，排序后 a 可能会出现在 b 的后面。

冒泡排序

比较相邻元素。如果第一个比第二个大，就交换他们两个。

public void bubbleSort(int[] nums) {
    int len = nums.length;
    for (int i = 0; i < len - 1; i++) {
        for (int j = 0; j < len - i - 1; j++) {
            if (nums[j] > nums[j + 1]) {
                int temp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = temp;
            }
        }
    }
}

快速排序

public void quickSort(int[] nums, int l, int r) {
    if (l < r) {
        int index = partition(nums, l, r);
        quickSort(nums, l, index - 1);
        quickSort(nums, index + 1, r);
    }
    return;
}
public int partition(int[] nums, int l, int r) {
    int index = nums[l];
    while (l < r) {
        while (l < r && nums[r] > index) {
            r--;
        }
        nums[l] = nums[r];
        while (l < r && nums[l] <= index) {
            l++;
        }
        nums[r] = nums[l];
    }
    nums[l] = index;
    return l;
}  

快速排序的优化

待排序列是部分有序时，固定选取枢轴使快排效率底下，要缓解这种情况，就要从基准的选取下手。

1. 随机选取法：使用随机数生成函数生成一个随机数 rand，随机数的范围为 [left, right]，并用此随机数为下标对应的元素 a[rand] 作为中轴，并与最后一个元素 a[right] 交换，然后进行快排。
2. 三数取中：假设数组被排序的范围为left和right，center=（left+right）/2，对a[left]、a[right]和a[center]进行适当排序，取中值为中轴，将最小者放 a[left]，最大者放在 a[right]，把中轴元与 a[right-1] 交换，并在分割阶段将i和j初始化为 left+1 和 right-2。然后使用双向描述法，进行快排。

上述三种快排，在处理重复数的时候，效率并没有很大提高，因此，我们可以想办法优化。

1. 当待排序序列长度分割到一定大小后，使用插入排序。因为对于规模很小的情况，快速排序的优势并不明显（可能没有优势），而递归型的算法还会带来额外的开销。
2. 在一次分割结束后，可以把与 Key 相等的元素聚在一起，继续下次分割时，不用再对与key相等元素分割（处理重复效率极高）。

插入排序

在已排序序列中从后向前扫描，找到相应位置插入。

public void insertSort(int[] nums) {
    int len = nums.length;
    for (int i = 1; i < len; i++) {
        int j = i;
        while (j - 1 >= 0 && nums[j] < nums[j - 1]) {
            swap(nums, j, j - 1);
            j--;
        }
    }
}
public void swap(int[] nums, int l, int r) {
    int temp = nums[l];
    nums[l] = nums[r];
    nums[r] = temp;
}

希尔排序

是第一个突破 O(n^2^) 的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

public void shellSort(int[] nums) {
    int len = nums.length;
    for (int gap = len; gap > 0; gap /= 2) {
        for (int i = gap; i < len; i++) {
            int j = i;
            while (j - gap >= 0 && nums[j] < nums[j - gap]) {
                swap(nums, j, j - gap);
                j -= gap;
            }
        }
    }
}
public void swap(int[] nums, int l, int r) {
    int temp = nums[l];
    nums[l] = nums[r];
    nums[r] = temp;
}

选择排序

在所有元素中找出最小的元素，放到起始位置，以此类推，直到所有元素排序完毕。

public void selectSort(int[] nums) {
    int len = nums.length;
    for (int i = 0; i < len - 1; i++) {
        int min = i;
        for (int j = i + 1; j < len; j++) {
            if (nums[j] < nums[min]) {
                min = j;
            }
        }
        swap(nums, i, min);
    }
}
public void swap(int[] nums, int l, int r) {
    int temp = nums[l];
    nums[l] = nums[r];
    nums[r] = temp;
}

堆排序

堆是一棵完全二叉树，子节点的值总是小于（大于）它的父节点。

• 堆的插入、删除元素时间复杂度都是 O(log n)。

• 建堆的时间复杂度是 O(n)。

• 堆排序的时间复杂度是 O(nlog n)。

利用大根堆建立升序序列的过程：

1. 先创建大根堆，从后往前遍历。
2. 将堆顶元素与最后一个元素交换，此时最大元素就在最后面。
3. 将堆继续调整为大根堆。
4. 每次取出堆顶元素换到后面，交换到最后面的元素就是有序的，反复操作就排好序了。

public void heapSort(int[] nums) {
    int len = nums.length;
    //建立大根堆
    for (int i = len / 2; i >= 0; i--) {
        heapify(nums, i, len);
    }
    //将最后一个元素与第一个元素交换，再次调整为大根堆
    for (int i = nums.length - 1; i > 0; i--) {
        swap(nums, 0, i);
        heapify(nums, 0, i);
    }
}
public void heapify(int[] nums, int root, int len) {
    //左子树位置
    int left = 2 * root + 1;
    //右子树位置
    int right = 2 * root + 2;
    int max = root;
    if (left < len && nums[left] > nums[max]) {
        max = left;
    }
    if (right < len && nums[right] > nums[max]) {
        max = right;
    }
    if (max != root) {
        swap(nums, max, root);
        heapify(nums, max, len);
    }
}
public void swap(int[] nums, int l, int r) {
    int temp = nums[l];
    nums[l] = nums[r];
    nums[r] = temp;
}

归并排序

归并排序是采用分治法的一个典型应用。将已排序的子序列合并，得到完全有序的序列。

public void mergeSort(int[] nums, int left, int right) {
    if (left >= right) {
        return;
    }
    int mid = (left + right) / 2;
    mergeSort(nums, left, mid);
    mergeSort(nums, mid + 1, right);
    merge(nums, left, mid, right);
}
public void merge(int[] nums, int left, int mid, int right) {
    int i = left, j = mid + 1, index = 0;
    int[] temp = new int[right - left + 1];
    while (i <= mid && j <= right) {
        if (nums[i] < nums[j]) {
            temp[index++] = nums[i++];
        } else {
            temp[index++] = nums[j++];
        }
    }
    while (i <= mid) {
        temp[index++] = nums[i++];
    }
    while (j <= right) {
        temp[index++] = nums[j++];
    }
    for (int k = 0; k < temp.length; k++) {
        nums[left + k] = temp[k];
    }
}

参考文章

• 十大经典排序算法（动图演示）
• 快速排序一步一步优化