数组排序

作者: 许宏川 | 来源:发表于2015-06-30 03:42 被阅读85次

iOS 各种排序
Java 数组的排序、逆序
java 数组和list排序
数组
2018-01-14
PHP排序算法
算法记录
选择排序
按照数组中的字符串顺序给另一个数组排序
排序问题

有一组整型数组：

int[] arr = {6, 5, 3, 7, 2, 4, 9, 0, 8, 1};

现在要对它进行从小到大的排序怎么做呢？
对数组进行排序的算法有很多，这篇文章讲讲比较著名的冒泡排序和快速排序。

冒泡排序##

大致思路：
冒泡排序指数组的元素两两进行比较，如果是从小到大，那么就让第一个元素和第二个元素进行比较，如果后者比前者大则两者互换位置。然后继续比较第二个元素和第三个元素。这样一轮比较下来就可以把最大的元素找出来并且排到了数组的最后。
如果数组有10个元素，两两进行比较那么会做9次比较。而因为一轮之后已经找到了最大的元素，第二轮比较只需对前面9个元素进行两两比较也就是做8次比较。第二轮会找出第二大的元素放在倒数第二的位置。同样第三轮会做7次比较找到第三大的元素放在倒数第三的位置。重复这样的步骤就可以对数组进行排序。

结合图片再过一遍思路：
首先会比较前两个元素，6比5大则把5和6交换位置。接着比较第二个和第三个元素，6比3大则交换位置，再比较第三和第四个元素，6比7小则什么都不做，再比较第四和第五个元素，7比4大交换位置。以此类推，第一次一共进行了9次两两比较，最后找出了最大的数9并放在最后。

进入第二轮，依然是从头开始。比较前两个5比3大交换位置，接着5比6小不用交换。6比2大交换位置，6比4大交换位置，6比7小不交换。因为在上一轮中已经找出最大的数9并且放在最后，所以这次只需要做8次两两比较把第二大的8找出来放在倒数第二的位置。

接着第三轮做7次两两比较找出第三大的7放在倒数第3的位置，第四轮做6次找出第四大的6放在倒数第四的位置。最终完成数组的排序。

具体代码实现方式如下：

//冒泡排序
static void bubbleSort(int[] arr) {

    for (int i = 0; i < arr.length - 1; i++) { //控制比较轮数

        for (int j = 0; j < arr.length - i - 1; j++) { //控制每轮的两两比较次数
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }

        }

    }

}

快速排序##

大致思路：
快速排序是先以数组中任意一个数为基准数。然后把数组一分为二，使其中一组的任意一个数都比另一组的任意一个数小。接着把两组数各自再用一个基准数再分解为二组，然后再分解，然后再分解。直到分不下去了（数组只有一个元素或者元素都相同）那么这些分解后的数组连起来就是一个有序的数组了。

结合图片再过一遍思路：
还是排成从小到大。以数组第一位6为基准数，然后从左往右找出比6大的数，并且从右往左找出比6小的数。但是必须从右边开始启动，也就是从1开始找比6小的数，然而1就比6小了。那么再5开始找比6大的数，知道碰到7，然后把7和1互换位置。

接着从刚才的位置开始继续找，还是从右边开始找比6小的数，也就是0。然后左边开始找比6大的数也就是9。然后交换9和0的位置。然后还会继续找，依然从右边开始找比6小的数，结果碰到9左右两边重合了查找结束。最后把基准数和0换个位置，那么就把数组分解为{0, 5, 3, 1, 2, 4}和{6, 9, 8, 7}。
注意这里说吧数组分解成两部分但并没有分成两个数组，代码里也不会创建新的数组来装这两部分，只不过形成的结果是数组下标为6及下标小于6的元素都比数组下表为7及下标大于7的元素小。
然后再把{0, 5, 3, 1, 2, 4}和{6, 9, 8, 7}各自再进行分解知道数组变得有序。

具体代码实现方式如下：

//快速排序
static void quickSort(int[] arr) {

    if (arr.length <= 1) {
        return;
    } else {
        partition(arr, 0, arr.length - 1);
    }


}

static void partition(int[] arr, int left, int right) {
    int i = left;
    int j = right;
    int pivotKey = arr[left]; //基准数

    while (i < j) {

        while (i < j && arr[j] >= pivotKey) {
            j--;
        }

        while (i < j && arr[i] <= pivotKey) {
            i++;
        }

        if (i < j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    if (i != left) {
        arr[left] = arr[i];
        arr[i] = pivotKey;
    }

    if (i - left > 1) {
        partition(arr, left, i - 1);
    }

    if (right - j > 1) {
        partition(arr, j + 1, right);
    }

}

其中冒泡排序的时间复杂度就是个双重循环，也就是O(N^{2)，而快速排序的每次比较都是跨越很大数组长度的比较，所以要比冒泡排序快得多。但是很不稳定，最差的情况也是两两进行比较，所以最差的时间复杂度是O(N}2)。平均时间复杂度是O(NlogN)。所以快速排序要比冒泡排序要快得多。
可以写一段测试代码，例如随机生成一个10000个元素的数组，然后看各自排序需要多长时间。

//随机生成数组元素
Random r = new Random();
for (int i = 0; i < arrLength; i++) {
    arr[i] = r.nextInt(arrLength);
}

long startTime = System.currentTimeMillis(); //保存排序前的时间
bubbleSort(arr);
System.out.println("冒泡排序用了：" + (System.currentTimeMillis() - startTime) +  "毫秒"); //输出所用瞬间

startTime = System.currentTimeMillis();
quickSort(arr);
System.out.println("快速排序用了：" + (System.currentTimeMillis() - startTime) +  "毫秒");

运行结果:

<pre>
冒泡排序用了：96毫秒
快速排序用了：14毫秒
</pre>

本文代码下载：百度网盘