排序

为什么要学习O(N^2)的排序算法

  • 是其他算法的基础
  • 编码简单
  • 作为子过程,用于改进复杂的排序算法

排序算法的稳定性

对于相等的元素,在排序后,相对位置没有发生改变

选择排序

202002070942

每一轮循环找到数组中最小的元素,第一次找到的最小元素将它与第一个元素交换位置,第二次找到的最小元素交换将它与第二个位置交换,以此类推

for (int i = 0; i < arr.length; i++) {
    // 寻找[i,n)里的最小值
    int min = i;
    for (int j = i + 1; j < arr.length; j++) {
        if (less(arr[j],arr[min])) {
            min = j;
        }
    }
    swap(arr, i, min);
}

插入排序

202002070926

插入排序是从后往前扫描的

第一次从后到前逐个扫描下标1-0的元素,如果发现后面一个比前面小,则两个交换位置,否则就开始下一次扫描

第二次从后到前逐个扫描下标2-0的元素,如果发现后面一个比前面小,则两个交换位置 ,否则就开始下一次扫描

依此类推

  • 插入排序对近乎有序的数组性能很强
for (int i = 1; i < a.length; i++) {
    // 从右到左扫描,如果右值小于左值,则交换,否则跳出本轮循环
    for (int j = i; j > 0; j--) {
        if (less(a[j], a[j - 1])) {
            swap(a, j, j - 1);
        }else {
            break;
        }
    }
}

// 改进后的插入排序
for (int i = 1; i < a.length; i++) {
    var e = a[i];
    int j;
    for (j = i; j > 0 && greater(a[j - 1], e); j--) {
        // 将
        a[j]=a[j-1];
    }
    a[j]=e;
}

冒泡排序

202002081000

第一次扫描下标为0的元素到最后一个元素

第二次扫描下标为0的元素到倒数第二个元素

每次扫描如果发现右边比左边小 则两个交换位置

以此类推

for (int i = 1; i < a.length; i++) {
    for (int j = 0; j < a.length - i; j++) {
        if (less(a[i],a[j])){
            swap(a,i,j);
        }
    }
}
// 改进的冒泡排序
for (int i = 1; i < a.length; i++) {
    int lastSwap = 1;
    for (int j = 0; j < a.length - i && j < lastSwap; j++) {
        if (less(a[i], a[j])) {
            swap(a, i, j);
            // 记录最后一次交换的位置,该位置后的元素在下一轮扫描后不会被扫描
            lastSwap = j;
        }
    }
}

希尔排序

202002081040

希尔排序是将插入排序中的交换相邻元素改为交换不相邻元素

  • 选择一个增量序列t1,t2,…,tk
  • 按增量序列个数k,对序列进行k 趟排序
int h = 1;
// 计算增长序列,1,4,13,40...
while (h < a.length / 3) {
    h = 3 * h + 1;
}
while (h>=1){
    for (int i = h; i < a.length; i++) {
        // 对第i,i-h,i-2*h,i-3*h进行插入排序
        var e = a[i];
        int j;
        for (j = i; j > h && less(a[j - h], e); j-=h) {
            a[j]=a[j-h];
        }
        a[j]=e;
    }
    h/=3;
}

归并排序

202002081126

  • 把长度为n的输入序列分成两个长度为n/2的子序列;
  • 对这两个子序列分别采用归并排序;
  • 将两个排序好的子序列合并成一个最终的排序序列

对两个有序子序列进行合并,得到一个更大的有序子序列,以此类推,直到只剩下一个序列

  • 但是一个缺点是需要额外的O(N)空间
private void mergeSort(Comparable<?>[] a, int l, int r) {
    if (l >= r) {
        return;
    }
    int mid = (l + r) / 2;
    mergeSort(a, l, mid); // 对左边排序
    mergeSort(a, mid + 1, r); // 对右边排序
    merge(a, l, mid, r); // 对两个数组进行归并
}
private void merge(Comparable<?>[] a, int l, int mid, int r) {
    // 开辟一块新空间给l-r之间的元素
    Comparable<?>[] aux = new Comparable<?>[r - l + 1];
    for (int i = l; i <= r; i++) {
        aux[i - l] = a[i];
    }

    int i = l, j = mid + 1;
    // 对l到r之间的元素进行扫描,将它们放到指定位置
    for (int k = l; k <= r; k++) {
        if (i > mid) { // 如果左指针已经跑过了mid,那此时让右指针去跑
            a[k] = aux[j - l];
            j++;
        } else if (j > r) { // 如果右指针已经跑完了,则此时让左指针去跑
            a[k] = aux[i - l];
            i++;
        } else if (less(a[i - l], a[j - l])) { // 否则就比较左右两指针谁的值比较小,谁小就把谁的值复制到结果里,然后该指针往后移动
            a[k] = aux[i - l];
            i++;
        } else {
            a[k] = aux[j - l];
            j++;
        }
    }
}

优化

当mid+1位置的元素大于mid位置的元素时,就没有必要进行归并了

if (greater(a[mid],a[mid+1])){
    merge(a, l, mid, r);
}

也可以当被归并排序的数组数量小于某一数量级时,使用其他排序算法,来提高性能

自底向上的归并排序

// 每次归并的数组大小依次为1 2 4 ...
for (int sz = 1; sz <= a.length; sz += sz) {
    for (int i = 0; i < a.length; i += sz + sz) {
        // 归并a[i...i+size-1] 与 a[i+size...i+2*size-1]
        if (i + sz < a.length) { // 只有左数组长度小于整个排序数组长度使(代表目前没有右数组),才进行归并(否则数组就是有序的了)
            merge(a, i, i + sz - 1, min(i + sz + sz - 1, a.length - 1));
        }
    }
}

快速排序

202002081411

选定一个元素,将比该元素小的元素放其左边,比它大的放在其右边,并递归地对它左右两边的子序列进行排序

  • 快速排序在最差的情况下,会退化为O(N^2)
private void quickSort(Comparable<?>[] a, int l, int r) {
    if (l >= r) {
        return;
    }
    int p = partition(a, l, r);
    quickSort(a, l, p - 1);
    quickSort(a, p + 1, r);
}

/**
 * 返回一个p,使得a[l...p-1] < a[p] 并且 a[p+1...r] > a[p]
 */
private int partition(Comparable<?>[] a, int l, int r) {
    var v = a[l];
    int j = l;
    // 从左到右扫描(一)
    for (int i = l + 1; i <= r; i++) {
        //如果扫描的元素小于v,则将该元素跟大数组的第一个元素交换,同时,小数组的位置扩张1(二)
        if (less(a[i], v)) {
            swap(a, j + 1, i);
            j++;
        }
    }
    // 最后,将v与小数组的最后一个元素交换位置(三)
    swap(a, l, j);
    return j;
}

批注 2020-02-08 134532

批注 2020-02-08 134637

批注 2020-02-08 134920

优化

当数组里有大量相同的元素,快速排序的时间复杂度为退化到N^2,解决方法是在两侧使用双指针向中间扫描

批注 2020-02-08 142132

  • 双路快速排序
private int partition(Comparable<?>[] a, int l, int r) {
    var v = a[l];
    // i:a[l+1...i] <=v  j:[j...r] >=v
    int i = l + 1, j = r;
    while (true) {
        while (i <= r && less(a[i], v)) i++;
        while (j >= l + 1 && greater(a[j], v)) j--;
        if (i > j) {
            break;
        } else {
            swap(a, i, j);
            i++;j--;
        }
    }
    swap(a,l,j);
    return j;
}
  • 三路快速排序
private void quickSort(Comparable[] a, int l, int r) {
    if (l >= r) {
        return;
    }

    // partition
    var v = a[l];

    int lt = l; // a[l+1...lt] < v
    int gt = r + 1; // a[gt...r] > v
    int i = l + 1; // a[lt+1...i) == v
    while (i < gt) {
        if (a[i].compareTo(v) < 0) {
            swap(a, i, lt + 1);
            lt++;
            i++;
        } else if (a[i].compareTo(v) > 0) {
            swap(a, i, gt - 1);
            gt--;
        }else {
            i++;
        }
    }
    swap(a,i,lt);

    quickSort(a, l, lt - 1);
    quickSort(a, gt, r);
}

归并排序与快速排序的背后

  • 两个算法都使用了分治算法

results matching " "

No results matching " "

results matching " "

No results matching " "