1341 2017-03-02 2020-06-25

一、概述

排序（Sorting）是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。

由于待排序的记录数量不同，使得排序过程中涉及的存储器不同，可将排序方法分为两大类：一类是内部排序，指的是待排序记录存放在计算机随机存储器中进行的排序过程；另一类是外部排序，指的是待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中需对外存进行访问的排序过程。

本篇讨论的是内部排序，其包含的排序算法大致如下图所示：

二、插入排序

1、直接插入排序

直接插入排序（Straight Insertion Sort）是一种最简单的排序算法，它的基本操作是将一个记录插入到已拍好的有序表中，从而得到一个新的、记录数增1的有序表。

1)排序示例：

 5 4 3 2 1 //先把5看作一个有序的序列
 4 5 3 2 1 //4比5小，所以要在5前面插入
 3 4 5 2 1 //3依次与5,4比较，最终插入在4前面
 2 3 4 5 1 //依次类推
 1 2 3 4 5

2）算法代码：

public static int[] straightInsertSort(int[] numbers) {
    for (int i = 1; i < numbers.length; i++) {
        if (numbers[i] < numbers[i - 1]) {
            int temp = numbers[i];
            int j = i - 1;
            for (;j >= 0 && numbers[j] > temp; j--) {
                numbers[j + 1] = numbers[j];
            }
            numbers[j + 1] = temp;
        }
    }
    return numbers;
}

3)算法分析：

• 稳定性：稳定。
• 空间复杂度：需要一个记录的辅助空间，为O(1)。
• 时间复杂度：取进行关键字比较次数和移动次数最大值和最小值的平均值，约为n^2/4，则时间复杂度为O(n^2)，最好情况下为O(n)。

2、其他插入排序

其他插入排序算法还有：2-路插入排序、表插入排序、希尔排序，这里点到为止，不做深究。

三、选择排序

1、冒泡排序

冒泡排序作为排序的必备基本功，这里只列出代码，不做赘述。

public static int[] bubbleSort(int[] numbers) {
    for(int i = 1; i < numbers.length; i++) {
        boolean needSwap = false;
        for (int j = 0; j < numbers.length - i; j++) {
            if (numbers[j] > numbers[j + 1]) {
                int temp = numbers[j];
                numbers[j] = numbers[j + 1];
                numbers[j + 1] = temp;
                needSwap = true;
            }
        }
        if (!needSwap) {//没有发生交换，已有序
            return numbers;
        }
    }
    return numbers;
}

算法分析：

• 稳定性：稳定。
• 空间复杂度：O(1)。
• 时间复杂度：最好情况下为O(n)，最坏情况为O(n^2)，平均情况为O(n^2)。
• 补充：和直接插入排序的所有属性几乎一样，是简单稳定的排序算法。

2、快速排序

快速排序（Quick Sort）是对冒泡排序的一种改进。它的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分的关键字比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。 1)排序示例：

6 1 2 7 9 3 4 5 10 8
//先通过一个临时变量记录6的值
//选取6为基点，通过high--先从后面往前找一个比6小的数，为5，此时high指向5，且使得arr[low] = arr[high] = 5，此时有
5 1 2 7 9 3 4 5 10 8
//接下来，通过low++从前面往后找一个比6大的数，为7，此时low指向7，且使得arr[high] = arr[low] = 7，此时有
5 1 2 7 9 3 4 7 10 8
//由于此时low指向上面的第一个7 < high指向第二个7，所以从后往前选取比6小的数，为4，且使得arr[low] = arr[high] = 4，此时有
5 1 2 4 9 3 4 7 10 8
//接下来，通过low++从前面往后找一个比6大的数，为9，此时low指向9，且使得arr[high] = arr[low] = 9，此时有
5 1 2 4 9 3 9 7 10 8
//由于此时low指向上面的第一个9 < high指向第二个9，所以从后往前选取比6小的数，为3，且使得arr[low] = arr[high] = 3，此时有
5 1 2 4 3 3 9 7 10 8
//此时low指向第一个3，high指向第二个3，接下来，通过low++从前面往后找一个比6大的数，此时找不到目标数，且low自增到high，即low = high，numbers[low] = pivot，有
5 1 2 4 3 6 9 7 10 8
//目标序列以6位中间值，一次排序完成，后续过程同理

2）算法代码：

public static void quickSort(int[] numbers, int low, int high) {
    if (low < high) {
        int pivotIndex = partition(numbers, low, high);
        quickSort(numbers, low, pivotIndex - 1);
        quickSort(numbers, pivotIndex + 1 , high);
    }
}

private static int partition(int[] numbers, int low, int high) {
    int pivot = numbers[low];
    while (low < high) {
        while (low < high && numbers[high] >= pivot) {
            high--;
        }
        numbers[low] = numbers[high];
        while (low < high && numbers[low] <= pivot) {
            low++;
        }
        numbers[high] = numbers[low];
    }
    numbers[low] = pivot;
    return low;
}

3)算法分析：

• 稳定：不稳定。
• 空间复杂度：O(nlog2n)。
• 时间复杂度：最好情况下为O(nlog2n)， 最坏情况为(n^2)，平均情况为O(nlog2n)。
• 补充：就平均时间而言，快速排序是目前被认为是最好的一种内部排序方法。

四、选择排序

1、简单选择排序

简单选择排序作为排序的必备基本功，这里只列出代码，不做赘述。

public static int[] selectSort(int[] numbers) {
    for (int i = 0; i < numbers.length - 1; i++) {
        int min = i;
        for (int j = min + 1; j < numbers.length; j++) {
            if (numbers[j] < numbers[min]) {
                min = j;
            }
        }
        if (i != min) {
            int temp = numbers[i];
            numbers[i] = numbers[min];
            numbers[min] = temp;
        }
    }
    return numbers;
}

算法分析：

• 稳定性：不稳定。
• 空间复杂度：O(1)。
• 时间复杂度：最好情况下为O(n^2)，最坏情况为O(n^2)，平均情况为O(n^2)。

五、其他排序

有待补充….

总访问次数: 101次, 一般般帅 创建于 2017-03-02, 最后更新于 2020-06-25