六个排序算法
六个排序算法
奋斗到天明 发表于2年前
六个排序算法
  • 发表于 2年前
  • 阅读 39
  • 收藏 7
  • 点赞 2
  • 评论 0

标题:腾讯云 新注册用户域名抢购1元起>>>   

摘要: 冒泡,选择,插入,归并,希尔,快速

排序算法

这是一共列表六个算法,冒泡,选择,插入,归并,希尔,快速,此外还有快速排序中枢选择不同的算法。

冒泡排序

最简单的排序方法了,从第一个元素循环到最后一个元素。对比相邻元素,前者小于后者时,交换两者,结果是让最后一个元素为最小值。重复这个动作,让无序部分中的最小者慢慢到无序部分的最后面。从而让整个数组从大到小排序。
效率上来说,平均情况是$O(N^2)$,最坏的情况也是$O(N^2)$

private static void pop(int[] array){
    for (int i = 0; i < array.length; i++) {
        for (int j = 0; j < array.length - i - 1; j++) {
            if(array[j] < array[j + 1]){
                swap(j + 1, j, array);
            }
        }
    }
}

选择排序

也是比较简单的排序方法,从第一个元素循环到最后一个元素。对比第一个元素与循环中下标元素,前者小于后者时,交换两者,结果是让第一个元素为最大值。用第二个,第三个,第N个重复这个动作,从无序部分挑出最大的元素,慢慢让整个数组从大到小排序。
效率上来说,平均情况是$O(N^2)$,最坏的情况也是$O(N^2)$

private static void select(int[] array){
    for (int i = 0; i < array.length; i++) {
        for (int j = i; j < array.length; j++) {
            if(array[i] < array[j]){
                swap(j, i, array);
            }
        }
    }
}

插入排序

插入排序比之前两个有难度。对于某个元素他假设左边所有元素都是有序的。现将该元素从右到左和有序部分每个元素对比,插入到他们之中的合适位置,让有序部分依 然有序。依次从无序部分中拿过一个元素插入到有序部分。最后整个数组都成了有序数组。
效率上来说,平均情况是$O(N^2)$,最坏的情况也是$O(N^2)$

private static void insert(int[] array){
    for (int i = 0; i < array.length; i++) {
        for (int j = i; j > 0; j--) {
            if(array[j - 1] < array[j]){
                swap(j - 1, j, array);
            }
        }
    }
}

归并排序

归并排序利用了递归原理。将数组分为两部分,然后让分别让这两部分有序,最后合并这两部分。这是大体逻辑,需要递归的是分别让这两部分有序,让他们再分再分……再分,最后只有一个元素时,就不再分,让递归外层的去合并,合并合并……合并。当整个数组合并时,他们都有序了。
效率上来说,平均情况是$O(NLogN)$,最坏的情况也是$O(NLogN)$,但是他需要额外的空间。

private static void merge(int[] array){
    int[] temp = new int[array.length];
    mergeCore(0, array.length - 1, temp, array);
}

private static void mergeCore(int left, int right, int[] temp, int[] array) {
    if(left == right){
        return;
    }else{
        int mid = (left + right) / 2;

        mergeCore(left, mid, temp, array);
        mergeCore(mid + 1, right, temp, array);

        mergeTogether(left, mid, right, temp, array);
    }
}

private static void mergeTogether(int left, int mid, int right, int[] temp, int[] array) {
    int curTemp = 0;
    int curLeft = left;
    int curRight = mid + 1;
    int size = right - left;
    while(curLeft <= mid && curRight <= right){
        if(array[curLeft] >= array[curRight]){
            temp[curTemp++] = array[curLeft++];
        }else{
            temp[curTemp++] = array[curRight++];
        }
    }

    while(curLeft <= mid){
        temp[curTemp++] = array[curLeft++];
    }

    while(curRight <= right){
        temp[curTemp++] = array[curRight++];
    }

    for (int i = 0; i <= size; i++) {
        array[left++] = temp[i];
    }
}

希尔排序

算是插入排序的变种,在插入排序中如果整个数组都是倒序,那么效率就很低下。而希尔排序是将有许部分,按间隔分组。如原来是1-2-3-4-5-6……,而希尔排序是分为两组1-3-5,2-4-5。分别进行插入排序,这样交换的次数会减少。然后慢慢减小间隔,再次排序,最后当间隔是1时,希尔排序就退化成插入排序了。这个过程中,每个元素会逐渐靠近合适的位置。
目前最合理间隔的算法是$n=(n-1)/3$
效率上来说,平均情况是$O(N^{3/2})$,最坏的情况也是$O(N^{3/2})$

private static void shell(int[] array){
    int salt = 1;
    while(salt < array.length / 3){
        salt = salt * 3 + 1;
    }

    while(salt > 0){
        for (int i = salt; i < array.length; i++) {
            for (int j = i ; j > salt - 1; j = j - salt) {
                int t;
                if(array[j - salt] < array[j]){
                    swap(j - salt, j, array);
                }
            }

        }
        salt = (salt - 1)/3;
    }
}

快速排序

六种中最快速的排序了。取无序数组中的一个元素为枢纽。然后让所有的元素与之相比,大于的放一边,小于的放一边。中间放该元素。将两边再次重复这个步骤,直到只剩下一个元素,这样再回归。最后所有元素都有序了。
这里取的是枢纽元素是最后面的元素。
效率上来说,平均情况是$O(N*LogN)$,最坏的情况是$O(N²)$

private static void fast(int[] array){
    fastCort(0, array.length - 1, array);
}

private static int calcMid(int left, int right, int[] array) {
    int mid = (left + right)/2;
    if(array[left] < array[mid]){
        swap(left, mid, array);
    }
    if(array[left] < array[right]){
        swap(left, right, array);
    }
    if(array[mid] < array[right]){
        swap(mid, right, array);
    }
    swap(mid,right - 1, array);
    return 0;
}

private static void fastCort(int left, int right, int[] array) {
    if(left < right){
        int pivot = array[right];
        int border = findBorder(left, right, pivot, array);
        fastCort(left, border - 1, array);
        fastCort(border + 1, right, array);
    }else{
        return;
    }
}

private static int findBorder(int left, int right, int pivot, int[] array) {
    int curLeft = left - 1;
    int curRight = right;
    while(true){
        while(array[++curLeft] > pivot)
            ;

        while(curRight > left && array[--curRight] < pivot)
            ;

        if(curLeft >= curRight){
            break;
        }else{
            swap(curRight, curLeft, array);
        }
    }
    swap(right, curLeft, array);

    return curLeft;

}

三项取中快速排序

与前面的原理一样,不过枢纽取是取最左边、最右边、中间。三个元素,然后排序,取值中间的元素为枢纽。再递归。

private static void fastMid(int[] array){
    fastMidCort(0, array.length - 1, array);
}

private static void fastMidCort(int left, int right, int[] array) {
    if(right - left < 3){
        lessSort(left, right, array);
    }else{
        int pivot = calcMid(left, right, array);
        int border = findBorderMid(left, right, pivot, array);
        fastMidCort(left, border - 1, array);
        fastMidCort(border + 1, right, array);
    }
}

private static int findBorderMid(int left, int right, int pivot, int[] array) {
    int curLeft = left;
    int curRight = right - 1;
    while(true){
        while (array[++left] > pivot)
            ;
        while(array[--right] < pivot)
            ;

        if(curLeft >= curRight){
            break;
        }else {
            swap(curLeft, curRight, array);
        }
    }
    swap(curLeft, right - 1, array);
    return curLeft;
}

private static void lessSort(int left, int right, int[] array) {
    if(right <= left){
        return;
    }else if(right - left < 2){
        if(array[left] < array[right]){
            swap(left, right, array);
        }
    }else{
        if(array[left] < array[left + 1]){
            swap(left, left + 1, array);
        }
        if(array[left] < array[right]){
            swap(left, right, array);
        }
        if(array[left + 1] < array[right]){
            swap(left + 1, right, array);
        }
    }
}

private static void swap(int a, int b, int[] array) {
    int t;
    t = array[b];
    array[b] = array[a];
    array[a] = t;
}
共有 人打赏支持
粉丝 18
博文 112
码字总数 82707
×
奋斗到天明
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: