基础算法之排序篇

相信所有人第一次学习算法都是从排序开始的，优秀的排序算法非常简洁且优雅。下面来介绍常见的排序算法。

一些名词：

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
稳定性：稳定的算法在排序的过程中不会改变元素彼此的位置的相对次序，反之不稳定的排序算法经常会改变这个次序。

排序算法时间空间复杂度表
sort

冒泡排序

算法思想

比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

public static void bubbleSort(int[] arr){
        for (int i = 1; i < arr.length; i++) {
            boolean flag = true;
            for (int j = 0; j < arr.length - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                    flag = false;
                }
            }
            if (flag) {
                break;
            }
        }
    }

选择排序

算法思想

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
重复第二步，直到所有元素均排序完毕。

public static void selectionSort(int[] arr){
        for (int i = 0; i < arr.length - 1; i++) {
            int min = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[min]) {
                    min = j;
                }
            }
            if (i != min) {
                int tmp = arr[i];
                arr[i] = arr[min];
                arr[min] = tmp;
            }
        }
    }

插入排序

算法思想

将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

public static void InsertSort(int[] arr){
        for (int i = 1; i < arr.length; i++) {
            int tmp = arr[i];
            int j = i;
            while (j > 0 && tmp < arr[j - 1]) {
                arr[j] = arr[j - 1];
                j--;
            }
            if (j != i) {
                arr[j] = tmp;
            }
        }
    }

希尔排序

算法思想

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。

public static void shellSort(int[] arr) {
        int length = arr.length;
        int temp;
        for (int step = length / 2; step >= 1; step /= 2) {
            for (int i = step; i < length; i++) 
                temp = arr[i];
                int j = i - step;
                while (j >= 0 && arr[j] > temp) {
                    arr[j + step] = arr[j];
                    j -= step;
                }
                arr[j + step] = temp;
            }
        }
    }

快速排序

算法思想

从数列中挑出一个元素，称为 “基准”;
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。
递归地把小于基准值元素的子数列和大于基准值元素的子数列排序；

void quick_sort(int a[], int l, int r) {
    if (l >= r) return ;
    int x = a[l + r >> 1], i = l - 1, j = r + 1;
    while(i < j) {
        do i ++ ; while(a[i] < x);
        do j -- ; while(a[j] > x);
        if (i < j)  swap(a[i], a[j]);
    }
    quick_sort(a, l, j);
    quick_sort(a, j + 1, r);
}

归并排序

算法思想

将待排序的数列分成若干个长度为1的子数列，然后将这些数列两两合并，直接合并成一个数列为止。

void merge_sort(int a[], int l, int r) {
    if (l >= r) return ;
    int mid = l + r >> 1;
    merge_sort(a, l, mid);
    merge_sort(a, mid + 1, r);
    
    int num = 0;
    int i = l, j = mid + 1;
    while(i <= mid && j <= r) {
        if (a[i] <= a[j])
            temp[num ++] = a[i ++];
        else
            temp[num ++] = a[j ++];
    }
    while(i <= mid) temp[num ++] = a[i ++];
    while(j <= r)   temp[num ++] = a[j ++];
    
    for (int i = l, j = 0; i <= r; i ++, j ++) {
        a[i] = temp[j];
    }
}

计数排序

算法思想

找出待排序的数组中最大和最小的元素
统计数组中每个值为 $i$ 的元素出现的次数，存入数组 $C$ 的第 $i$ 项
对所有的计数累加（从 $C$ 中的第一个元素开始，每一项和前一项相加）
反向填充目标数组：将每个元素i放在新数组的第 $C(i)$ 项，每放一个元素就将 $C(i)$ 减去 $1$

public static void countSort(int[] a, int[] b) {
        int k = Arrays.stream(a).max().getAsInt();
        int[] c = new int[k + 1];
        for (int i = 0; i < k; i++) {
            c[i] = 0;
        }
        for (int i = 0; i < a.length; i++) {
            c[a[i]]++;
        }
        for (int i = 1; i <= k; i++) {
            c[i] += c[i - 1];
        }
        for (int i = a.length - 1; i >= 0; i--) {
            b[c[a[i]] - 1] = a[i];
            c[a[i]]--;
        }
    }

桶排序

算法思想

将数组通过映射函数分到有限数量的桶里
每个桶再个别排序
最后依次把各个桶中的记录列出来记得到有序序列

public static void bucketSort(int[] arr) {

        int max = Arrays.stream(arr).max().getAsInt();
        int min = Arrays.stream(arr).min().getAsInt();

        // 创建初始的桶
        int bucketNum = (max - min) / arr.length + 1;
        ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);

        for (int i = 0; i < bucketNum; i ++) {
            bucketArr.add(new ArrayList<>());
        }
        for (int i = 0, len = arr.length; i < len; i ++) {
            int num = (arr[i] - min) / arr.length;    //相同的商在同一个桶中
            bucketArr.get(num).add(arr[i]);     //根据商的不同，放入不同的桶
        }

        for (int i = 0; i < bucketArr.size(); i ++) {
            Collections.sort(bucketArr.get(i));
        }
    }

基数排序

算法思想

将整数按位数切割成不同的数字，然后按每个位数分别比较。

    public static void radixSorting(int[] arr) {
        for (int i = 0; i < 4; i++) {
            arr = countingSort(arr, i);
        }
    }

    public static int[] countingSort(int[] arr, int index) {
        int k = 9;
        int[] b = new int[arr.length];
        int[] c = new int[k + 1];

        for (int i = 0; i < k; i++) {
            c[i] = 0;
        }
        for (int i = 0; i < arr.length; i++) {
            int d = getBitData(arr[i], index);
            c[d]++;
        }
        for (int i = 1; i <= k; i++) {
            c[i] += c[i - 1];
        }
        for (int i = arr.length - 1; i >= 0; i--) {
            int d = getBitData(arr[i], index);
            b[c[d] - 1] = arr[i];
            c[d]--;
        }
        return b;
    }

    public static int getBitData(int data, int index) {
        while (data != 0 && index > 0) {
            data /= 10;
            index--;
        }
        return data % 10;
    }

堆排序

算法思想

初始化堆：将数列a[1...n]调整为大根堆。
交换数据：将a[1]和a[n]交换，使a[n]是a[1...n]中的最大值；然后将a[1...n-1]重新调整为大根堆。依次类推，直到整个数列都是有序的。

public static void sort(int[] arr) {
        //1.构建大顶堆
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            //从第一个非叶子结点从下至上，从右至左调整结构
            adjustHeap(arr, i, arr.length);
        }
        //2.调整堆结构+交换堆顶元素与末尾元素
        for (int j = arr.length - 1; j > 0; j--) {
 
            //将堆顶元素与末尾元素进行交换
            int temp = arr[0];
            arr[0] = arr[j];
            arr[j] = temp;
            adjustHeap(arr, 0, j);//重新对堆进行调整
        }
    }
 
    public static void adjustHeap(int[] arr, int i, int length) {
        int temp = arr[i];//先取出当前元素i
        for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {//从i结点的左子结点开始，也就是2i+1处开始
            if (k + 1 < length && arr[k] < arr[k + 1]) {//如果左子结点小于右子结点，k指向右子结点
                k++;
            }
            if (arr[k] > temp) {//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
                arr[i] = arr[k];
                i = k;
            } else {
                break;
            }
        }
        arr[i] = temp;//将temp值放到最终的位置
    }

Q.E.D.

框框‘s blog

一些名词：

冒泡排序

算法思想

选择排序

算法思想

插入排序

算法思想

希尔排序

算法思想

快速排序

算法思想

归并排序

算法思想

计数排序

算法思想

桶排序

算法思想

基数排序

算法思想

堆排序

算法思想

Linux之常用命令

具体数学——第一章

框框