排序算法

作者: 新许88 | 来源:发表于2019-10-22 16:12 被阅读0次

java实现快速排序、归并排序、希尔排序、基数排序算法...
web开发需要知道的几个算法
算法学习(1)-排序算法
经典排序算法总结
前端算法学习-第一篇
七大排序算法之冒泡排序
算法-选择排序
浅谈排序算法
线性排序
算法4：插入排序和选择排序算法的比较

1. 冒泡排序
2. 鸡尾酒排序(双向冒泡排序)
3. 快速排序(Quicksort)
- 3.1. 参考文章

1. 冒泡排序

两个数比较大小，较大的数下沉，较小的数冒起来。
这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。
1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

1.1. 基础版本

image

    public static void bubbleSort(int[] arr) {
        int temp;// 临时变量
        for (int i = 0; i < arr.length - 1; i++) { // 表示趟数，一共arr.length-1次。
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    temp = arr[j + 1];
                    arr[j + 1] = arr[j];
                    arr[j] = temp;
                }
            }
        }
    }
/**
    第1轮后: [3, 1, 4, 2, 7, 8, 6, 5, 9]
    第2轮后: [1, 3, 2, 4, 7, 6, 5, 8, 9]
    第3轮后: [1, 2, 3, 4, 6, 5, 7, 8, 9]
    第4轮后: [1, 2, 3, 4, 5, 6, 7, 8, 9]
    第5轮后: [1, 2, 3, 4, 5, 6, 7, 8, 9]
    第6轮后: [1, 2, 3, 4, 5, 6, 7, 8, 9]
    第7轮后: [1, 2, 3, 4, 5, 6, 7, 8, 9]
    第8轮后: [1, 2, 3, 4, 5, 6, 7, 8, 9]
**/

一共两层循环，最后一位元素没有下一位元素，所以第一层循环arr.length-1次
外层每循环一次，有序区域就加一，所以内层循环就少循环一次

1.2. 优化一：设置标志位

针对问题：
数据的顺序排好之后，冒泡算法仍然会继续进行下一轮的比较，直到arr.length-1次，后面的比较没有意义的。

方案：
设置标志位flag，如果发生了交换flag设置为true；如果没有交换就设置为false。
这样当一轮比较结束后如果flag仍为false，即：这一轮没有发生交换，说明数据的顺序已经排好，没有必要继续进行下去。

    public static void bubbleSort(int[] arr) {
        int temp;// 临时变量
        boolean flag;// 是否交换的标志
        for (int i = 0; i < arr.length - 1; i++) { // 表示趟数，一共arr.length-1次。
            // 每次遍历标志位都要先置为false，才能判断后面的元素是否发生了交换
            flag = false;
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    temp = arr[j + 1];
                    arr[j + 1] = arr[j];
                    arr[j] = temp;
                    flag = true; // 只要有发生了交换，flag就置为true
                }
            }
            // 判断标志位是否为false，如果为false，说明后面的元素已经有序，就直接return
            if (!flag) {
                break;
            }
        }
    }

1.3. 优化二

按照现有的逻辑，有序区的长度和排序的轮数是相等的。比如第一轮排序过后的有序区长度是1，第二轮排序过后的有序区长度是2 ......

实际上，数列真正的有序区可能会大于这个长度，比如例子中仅仅第二轮，后面5个元素实际都已经属于有序区。因此后面的许多次元素比较是没有意义的。

如何避免这种情况呢？我们可以在每一轮排序的最后，记录下最后一次元素交换的位置，那个位置也就是无序数列的边界，再往后就是有序区了

public class BubbleSort {

    private static void sort(int[] array) {

        int tmp = 0;
        // 记录最后一次交换的位置
        int lastExchangeIndex = 0;
        // 无序数列的边界，每次比较只需要比到这里为止
        int sortBorder = array.length - 1;
        for (int i = 0; i < array.length; i++) {
            // 有序标记，每一轮的初始是true
            boolean isSorted = true;
            for (int j = 0; j < sortBorder; j++) {
                if (array[j] > array[j + 1]) {
                    tmp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = tmp;
                    // 有元素交换，所以不是有序，标记变为false
                    isSorted = false;
                    // 把无序数列的边界更新为最后一次交换元素的位置
                    lastExchangeIndex = j;
                }
            }
            sortBorder = lastExchangeIndex;
            if (isSorted) {
                break;
            }
        }
    }

    public static void main(String[] args) {
        int[] array = new int[] { 3, 4, 2, 1, 5, 6, 7, 8, 9 };
        sort(array);
        System.out.println(Arrays.toString(array));
    }
}

1.4. 参考文章

https://www.runoob.com/w3cnote/sort-algorithm-summary.html
https://blog.csdn.net/Abel_Liujinquan/article/details/88880483
https://blog.csdn.net/wubingju93123/article/details/81215984

2. 鸡尾酒排序(双向冒泡排序)

和传统冒泡的比较：不同的地方在于双向冒泡排序从低到高然后从高到低，而冒泡排序每次都是从低到高去比较序列里的每个元素。可以得到比冒泡排序稍微好一点的效能，原因是冒泡排序只能从一个方向进行比对，每次循环只移动一个项目

下面是双向冒泡排序的演示图：

image

设置一个左边标志位 left 和右边标志位 right ，每次先从左起向右冒泡，然后反过来从右起向左冒泡，并将 left 加一，right 减一，结束一次循环，以此循环直到不满足条件 left < right ，排序结束。示例代码如下：

public static void main(String[] args) {
        /**
        * 冒泡排序优化三：双向冒泡排序(鸡尾酒排序)
        */

        int[] a={3,2,5,8,4,7,6,9};
        int left = 0;
        int right = a.length - 1;
        int temp;

        while(left < right) {
            for(int i=left; i<right; i++) {         //找到当前排序元素里最大的那个，放在右侧
                if(a[i] > a[i+1]) {
                    temp = a[i];
                    a[i] = a[i+1];
                    a[i+1] = temp;
                }
            }
            right--;

            for(int j=right; j>left; j--) {         //找到当前排序元素里最小的那个，放在左侧
                if(a[j]<a[j-1]) {
                    temp = a[j];
                    a[j] = a[j-1];
                    a[j-1] = temp;
                }
            }
            left++;
        }
        for(int aa: a) {
            System.out.println(aa);
        }
    }

3. 快速排序(Quicksort)

先从数列中取出一个数作为key值；
将比这个数小的数全部放在它的左边，大于或等于它的数全部放在它的右边；
对左右两个小数列重复第二步，直至各区间只有1个数。

public class BubbleSort {

    public static void quickSort(int a[], int l, int r) {
        if (l >= r) {
            return;
        }

        int i = l;
        int j = r;
        int key = a[l];// 选择第一个数为key

        while (i < j) {

            while (i < j && a[j] >= key) {// 从右向左找第一个小于key的值
                j--;
            }
            if (i < j) {
                a[i] = a[j];
                i++;
            }

            while (i < j && a[i] < key) {// 从左向右找第一个大于key的值
                i++;
            }
            if (i < j) {
                a[j] = a[i];
                j--;
            }
        }
        // i == j
        a[i] = key;
        quickSort(a, l, i - 1);// 递归调用
        quickSort(a, i + 1, r);// 递归调用
    }

    public static void main(String[] args) {
        int[] arr = { 49, 38, 65, 97, 23, 22, 76, 1, 5, 8, 2, 0, -1, 22 };
        quickSort(arr, 0, arr.length - 1);
        System.out.println("排序后:" + Arrays.toString(arr));

    }
}