排序算法总结

排序算法总结

总览

• 稳定：排序前后相等元素之间的相对位置不变
• 不稳定：排序前后相等元素的相对位置发生变化
• 内排序：所有排序操作在内存中完成
• 外排序：排序方法通过磁盘和内存的数据传输对大数据进行排序

• 比较排序：在排序的最终结果里，元素之间的次序依赖于它们之间的比较，每个数必须与其他数进行比较，才能确定自己的位置，其优势在于，适用于各种规模的数据，不在乎数据的分布。比较排序适用于一切需要排序的情况。

常见的快速排序、归并排序、堆排序、冒泡排序等属于比较排序。

• 非比较排序：只确定每个元素之前的已有元素个数即可进行排序，一次遍历即可解决，非比较排序时间复杂度低，但由于非比较排序需要占用空间来确定唯一位置，所以对数据规模和数据分布有一定的要求。

基数排序、计数排序、桶排序属于非比较排序。

一、冒泡排序

简单的排序算法，通过重复遍历需要排序的数组，比较相邻元素的大小并交换位置，一次遍历使一个元素归位到数组末端。

代码

package sortalgorithms;
import java.util.Arrays;

public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {1, 5, 8, 2, 6, -3, 0, 7, -3, 3, 4, 9};
        bubbleSort(arr);
        System.out.println(Arrays.toString(arr));
        //[-3, -3, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    }

    public static void bubbleSort(int[] arr) {
        boolean flag = false;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    flag = true;
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                }
            }
            //若某次内层循环没有进行交换操作，则说明已经有序，可直接退出循环
            if (flag)
                flag = false;
            else
                break;
        }
    }
}

分析

空间复杂度O(1)

时间复杂度O(n^2^)

二、选择排序

表现最稳定的排序算法之一，总是O(n^2^)的时间复杂度，一般在数据规模较小的时候使用。其首先在未排序的序列中找到最小元素，将其放在序列起始位置，再从剩余未排序元素中继续寻找最小元素，放到已排序序列队尾，以此类推，直至排序完毕。

代码

package sortalgorithms;
import java.util.Arrays;

public class SelectSort {
    public static void main(String[] args) {
        int[] arr = {1, 5, 8, 2, 6, -3, 0, 7, -3, 3, 4, 9};
        selectSort(arr);
        System.out.println(Arrays.toString(arr));
        //[-3, -3, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    }

    private static void selectSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int minIndex = i;
            for (int j = i; j < arr.length; j++) {
                if (arr[j] < arr[minIndex])
                    minIndex = j;
            }
            int tmp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = tmp;
        }
    }
}

分析

空间复杂度O(1)

时间复杂度O(n^2^)

三、插入排序

通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

代码

package sortalgorithms;
import java.util.Arrays;

public class InsertSort {
    public static void main(String[] args) {
        int[] arr = {-2, -3, 1, 9, 3, 0, 5, 2, 4, 7, 6, 8};
        insertSort(arr);
        System.out.println(Arrays.toString(arr));
        //[-3, -2, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    }

    private static void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int current = arr[i];
            int index = i - 1;
            while (index >= 0 && current < arr[index]) {
                arr[index + 1] = arr[index];
                index--;
            }
            arr[index + 1] = current;
        }
    }
}

分析

空间复杂度O(1)

时间复杂度O(n^2^)

四、快速排序（重要）

通过一次排序将待排数据分隔为两部分，一部分数据均比另一部分数据小，再分别在两部分数据中继续排序，最后达到整体有序。

1、算法先从序列中挑出一个元素作为基准，然后将序列中所有比其小的元素放在左边，大的放在右边，即确定该基准在序列中的位置。

2、再递归地把小于基准值元素的子序列和大于基准值元素的子序列排序。

代码

package sortalgorithms;
import java.util.Arrays;

public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {-3, -2, 0, 5, 2, 7, 4, 1, 3, 9, 8, 6};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
        //[-3, -2, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    }

    private static void quickSort(int[] arr, int left, int right) {
        if (left > right)
            return;
        int l = left, r = right;
        //一般设首位为基准值
        int base = arr[left];
        while (l < r) {
            //寻找比base大的数准备交换
            while (arr[l] <= base && l < r)
                l++;
            //寻找比base小的数准备交换
            while (arr[r] >= base && l <= r)
                r--;
            //交换需保证l<r，否则直接退出，交换base和arr[r]
            if (l < r) {
                int tmp = arr[l];
                arr[l] = arr[r];
                arr[r] = tmp;
            }
        }
        //确定了base排序后的位置，交换
        arr[left] = arr[r];
        arr[r] = base;
        //分别对两部分进行快速排序
        quickSort(arr, left, r - 1);
        quickSort(arr, r + 1, right);
    }
}

分析

空间复杂度O(logn)

时间复杂度O(nlogn)

五、归并排序（重要）

建立在归并操作上的一种有效的排序算法，是分治法的一个典型应用。

1、算法先将长度为n的序列分为两个n/2的子序列，再对子序列分别进行归并排序。

2、然后将两个排序好的子序列合并为最终的有序序列。

代码

package sortalgorithms;
import java.util.Arrays;

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {1, 5, 8, 2, 6, -3, 0, 7, -3, 3, 4, 9};
        mergeSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
        //[-3, -3, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    }

    public static void mergeSort(int[] arr, int left, int right) {
        int mid = (right + left) / 2;
        if (left < right) {
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            merge(arr, left, mid, right);
        }
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        //初始化，i指向左半部分的起始，j指向右半部分起始索引位置mid+1
        int i = left, j = mid + 1;
        int t = 0;
        int[] tmp = new int[right + 1];
        while (i <= mid && j <= right) {
            if (i <= mid && arr[i] <= arr[j])
                //左半部分所指元素<右半部分所指元素
                tmp[t++] = arr[i++];
            else
                tmp[t++] = arr[j++];
        }
        while (i <= mid) {
            //右半部分元素已经全部处理完毕，剩余左半部分
            tmp[t++] = arr[i++];
        }
        while (j <= right) {
            //左半部分元素已经全部处理完毕，剩余右半部分
            tmp[t++] = arr[j++];
        }

        int index = left;
        t = 0;
        while (index <= right) {
            arr[index++] = tmp[t++];
        }
    }
}

分析

空间复杂度O(n)

时间复杂度O(nlogn)

六、堆排序（重要）

利用堆的数据结构所设计的一种排序算法，堆是一个近似完全二叉树的结构，子节点的键值或索引总是小于（或大于）其父节点。

将堆的逻辑结构映射到数组中，则有以下性质：

• 对于大顶堆：arr[i] >= arr[2i + 1] && arr[i] >= arr[2i + 2]

• 对于小顶堆：arr[i] <= arr[2i + 1] && arr[i] <= arr[2i + 2]

1、 将带排序的序列构造成一个大顶堆，根据大顶堆的性质，当前堆的根节点（堆顶）就是序列中最大的元素。

2、将堆顶元素和最后一个元素交换，然后将剩下的节点重新构造成一个大顶堆。

3、重复步骤2，如此反复，从第一次构建大顶堆开始，每一次构建，我们都能获得一个序列的最大值，然后把它放到大顶堆的尾部。最后，就得到一个有序的序列。

代码

package sortalgorithms;
import java.util.Arrays;

public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {-2, -3, 1, 9, 3, 0, 5, 2, 4, 7, 6, 8};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
        //[-3, -2, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    }

    private static void heapSort(int[] arr) {
        int len = arr.length;
        //构建大顶堆，将待排序序列，变成一个大顶堆结构的数组
        buildMaxHeap(arr, len);

        //交换堆顶和当前末尾的节点，调整大顶堆
        while (len > 0) {
            swap(arr, 0, len - 1);
            len--;
            adjustHeap(arr, 0, len);
        }
    }

    private static void buildMaxHeap(int[] arr, int len) {
        //从最后一个非叶节点开始向前遍历，调整节点性质，使之成为大顶堆
        for (int i = (len / 2 - 1); i >= 0; i--) {
            adjustHeap(arr, i, len);
        }
    }

    private static void adjustHeap(int[] arr, int i, int len) {
        //根据堆性质，找出其左右节点的索引
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        //默认当前节点（父节点）是最大值
        int maxIndex = i;
        if (left < len && arr[left] > arr[maxIndex])
            //若有左节点，且左节点值更大，更新最大值索引
            maxIndex = left;
        if (right < len && arr[right] > arr[maxIndex])
            //若有右节点，且右节点值更大，更新最大值索引
            maxIndex = right;
        if (maxIndex != i) {
            //若最大值不是当前非叶子节点的值，将当前节点和最大值的子节点互换,并调整堆
            swap(arr, i, maxIndex);
            adjustHeap(arr, maxIndex, len);
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

}

分析

空间复杂度O(1)

时间复杂度O(nlogn)

七、希尔排序

希尔排序是一种插入排序，是简单插入排序的改进，也称为缩小增量排序。算法将数据按一定增量分组，对每组使用直接插入排序算法排序，随着增量逐渐减少，每组包含的数据越来越多，当增量减至1时，排序完毕。

代码

package sortalgorithms;
import java.util.Arrays;

public class ShellSort {
    public static void main(String[] args) {
        int[] arr = {-2, -3, 1, 9, 3, 0, 5, 2, 4, 7, 6, 8};
        shellSort(arr);
        System.out.println(Arrays.toString(arr));
        //[-3, -2, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    }

    private static void shellSort(int[] arr) {
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                int index = i;
                int tmp = arr[i];
                while (index - gap >= 0 && tmp < arr[index - gap]) {
                    arr[index] = arr[index - gap];
                    index -= gap;
                }
                arr[index] = tmp;
            }
        }
    }
}

分析

空间复杂度O(1)

时间复杂度O(nlog^2^n)~O(n^1.3–2^)

八、计数排序

计数排序使用一个额外的数组tmp，其中第i个元素时待排序数组arr中值等于i的元素的个数，然后根据数组tmp来将arr中的元素排到正确的位置。

计数排序只能对整数进行排序。

1、找出待排序数组中最大和最小的元素。

2、统计数组中每个元素i出现的次数，存入数组tmp的第i项。

3、对所有的计数累加，反向填充目标数组。

代码

package sortalgorithms;
import java.util.Arrays;

public class CountingSort {
    public static void main(String[] args) {
        int[] arr = {-2, -3, 1, 9, 3, 0, 5, 2, 4, 7, 6, 8};
        countingSort(arr);
        System.out.println(Arrays.toString(arr));
        //[-3, -2, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    }

    private static void countingSort(int[] arr) {
        //定义两个变量来存放数组中的最大最小值
        int min = arr[0], max = arr[0];
        int len = arr.length;
        for (int i = 1; i < len; i++) {
            if (max < arr[i])
                max = arr[i];
            if (min > arr[i])
                min = arr[i];
        }
        //定义一个长度为n的数组，存储待排序元素
        int n = max - min + 1;
        int[] tmp = new int[n];
        //哪个数字出现一次，就将该数字作为下标存起来，例如2020出现了一次，就将tmp[2020]加一
        for (int i = 0; i < len; i++)
            tmp[arr[i] - min]++;
        int k = 0;
        //对tmp进行遍历，tmp[i]的值为i出现的次数
        for (int i = 0; i < n; i++) {
            for (int j = tmp[i]; j > 0; j--)
                arr[k++] = i + min;
        }
    }
}

空间复杂度O(n)

时间复杂度O(n)

九、基数排序

非比较排序算法，基数排序按照低位先排序，然后收集；再按照高位排序，收集；以此类推，直至最高位。

基数排序的两种方式：

• 高位优先，又称为最有效键(MSD),它的比较方向是由右至左；

• 低位优先，又称为最无效键(LSD),它的比较方向是由左至右；

基数排序只能对自然数进行排序。

1、取得数组中的最大数，并取得位数。

2、arr为原始数组，从最低位开始取每个位组成radix数组。

3、对radix进行计数排序

代码

package sortalgorithms;
import java.util.Arrays;

public class RadixSort {
    public static void main(String[] args) {
        int[] arr = {12, 13, 1, 9, 3, 0, 5, 2, 4, 7, 6, 8};
        radixSort(arr);
        System.out.println(Arrays.toString(arr));
        //[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 12, 13]
    }

    private static void radixSort(int[] arr) {
        //待排序列最大值
        int max = arr[0];
        int exp;//指数
        //计算最大值
        for (int anArr : arr) {
            if (anArr > max)
                max = anArr;
        }
        //从个位开始，对数组进行排序
        for (exp = 1; max / exp > 0; exp *= 10) {
            //存储待排元素的临时数组
            int[] temp = new int[arr.length];
            //分桶个数
            int[] buckets = new int[10];
            //将数据出现的次数存储在buckets中
            for (int value : arr)
                //(value / exp) % 10 :value的最底位(个位)
                buckets[(value / exp) % 10]++;
            //更改buckets[i]，
            for (int i = 1; i < 10; i++)
                buckets[i] += buckets[i - 1];
            //将数据存储到临时数组temp中
            for (int i = arr.length - 1; i >= 0; i--) {
                temp[buckets[(arr[i] / exp) % 10] - 1] = arr[i];
                buckets[(arr[i] / exp) % 10]--;
            }
            //将有序元素temp赋给arr
            System.arraycopy(temp, 0, arr, 0, arr.length);
        }
    }
}

分析

空间复杂度O(n)

时间复杂度O(n)

十、桶排序

桶排序就是把最大值和最小值之间的数进行瓜分，例如分成 10 个区间，10个区间对应10个桶，我们把各元素放到对应区间的桶中去，再对每个桶中的数进行排序，可以采用归并排序，也可以采用快速排序之类的。

之后每个桶里面的数据就是有序的了，我们在进行合并汇总。

代码

package sortalgorithms;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class BucketSort {
    public static void main(String[] args) {
        int[] arr = {12, 13, 1, 9, 3, 0, 5, 2, 4, 7, 6, 8};
        bucketSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void bucketSort(int[] arr) {
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;

        for(int i=0; i<arr.length; i++) {
            min = Math.min(arr[i], min);
            max = Math.max(arr[i], max);
        }

        //初始化桶
        int bucketSize = (max-min)/arr.length + 1;
        ArrayList<ArrayList<Integer>> bucket = new ArrayList<>(bucketSize);
        for(int i=0; i<bucketSize; i++)
            bucket.add(new ArrayList<>());

        //将每个元素放入桶中
        for(int i=0; i<arr.length; i++) {
            int num = (arr[i] - min)/arr.length;
            bucket.get(num).add(arr[i]);
        }

        //每个桶中的元素排序
        for(int i=0; i<bucketSize; i++)
            Collections.sort(bucket.get(i));

        //将排序好的数据合并汇总至原数组
        int k = 0;
        for(int i=0; i<bucketSize; i++) {
            for(int num : bucket.get(i))
                arr[k++] = min + num;
        }
    }
}

分析

空间复杂度O(n)

时间复杂度O(n)