几个常用的排序算法

将几个常用的算法，使用Java代码书写了一遍。其中每一种算法的思想、复杂度、稳定性在网上随处可见，因此本文只做一个简单的叙述；主要说一说，在手撸代码的时候，想起每一个算法的关键点，那么就可以快速的进行代码的书写。

先将排序中用到的一些代码先行写出，方便后续排序中代码的理解。

测试程序

用于测试排序结果的正确性，数组的大小可以根据自己的需求选择；数据的范围自己确定可以生成相应的随机数；可以记录系统的时间，测试排序过程所用到的时间。

import java.util.Random;

/**
 * @author: wooch
 * @create: 2020/02/11
 */
public class TestSort {
    public static void main(String[] args) {
        int len = 13;
        int[] arr = new int[len];
        Random random = new Random();
        for (int i = 0; i < len; i++) {
            arr[i] = random.nextInt(33) + 1;
        }

        TenSort ts = new TenSort();

        System.out.println("排序前：");
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println("
开始排序");

        long startTime = System.currentTimeMillis();

        //ts.bubbleSort(arr);//7ms
        //ts.selectSort(arr);//6ms
        //ts.insertSort(arr);//8ms
        //ts.shellSort(arr);//1ms
        //ts.quickSort(arr);
        //ts.mergeSort(arr);
        ts.heapSort(arr);


        long endTime = System.currentTimeMillis();
        System.out.println("
排序所用时间：" + (endTime - startTime) + "ms");

        System.out.println("排序后：");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

排序算法中的两个函数

一个swap函数，用于交换数组中两个数的位置；printArr函数，可以在在排序过程中使用，查看某一趟的排序结果。

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

private void printArr(int[] arr) {
    for (int num : arr) {
        System.out.print(num + " ");
    }
    System.out.println();
}

冒泡排序

每一趟排序就是将最大的数据放入到数组的最后。因此关键点有两个：

1. 会有多少趟排序，答案为【数组长度-1】趟就够了。换个角度想，最后一个数肯定是数组中最小的，肯定放在数组的第一位，因此不用在排一次序，此时最后一趟可以取消掉，因此只需要【数组长度-1】趟排序。
2. 每一趟排序的过程中将最大的数选出来，并且放到数组在该趟的最后位置。例如第一趟肯定选择是最大的数据，那么放在数组的最后一个位置，那么下标为【数组长度-1】，当趟数i是从1开始计数的时候，最后的【j+1】自然就是该趟的最后一个位置。

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

因此冒泡排序的关键点就是每次将最大的数放在未排序数组部分的最后一个位置就可以了。

关于优化：当整个数组已经有序的时候，那么第二个for循环内部的swap函数就不会产生作用，那么就以标志整个冒泡排序已经可以结束了。因此使用一个flag标志来确定排序过程中已经有序的时候就应该结束，而不是继续进行比较浪费时间和资源。

选择排序

个人认为其思想其实与冒泡有些类似，冒泡是将（最大或者最小）数沉底，而选择则是将（最大或者最小）数选择出来，从数组开始位置放置。只是没有每次对数据进行交换，而是记录其下标，最后只是交换一次数据。

/**
 * 选择排序
 *
 * @param arr
 */
public void selectSort(int[] arr) {
    int len = arr.length;
    int min = 0;
    int i = 0;
    while (i < len - 1) {
        min = i;
        for (int j = i + 1; j < len; j++) {
            min = arr[min] <= arr[j] ? min : j;
        }
        swap(arr, i, min);
        i++;
    }
}

因此选择排序，那么就是选择数据的下标，然后进行一次交换。

如果每次进行交换数据的话，那么可以很简单的成为冒泡的一种另类写法，将沉底变成浮顶。

快速排序

感觉这是面试过程中经常让撸的一个排序算法。个人认为有以下几个原因：

1. 原理简单：找一个标志，小的放左边，大的放右边。
2. 直接考察算法是否具有稳定性：具有稳定性，当数据相等的时候，不进行交换，那么最后的排序结果依然是具有稳定性的，这个可以是在代码中确定。
3. 代码强度：相比冒泡要复杂一些，但是比起归并和堆排序，有要简单一些，并且是平时中使用的较多的排序算法。
4. 考察了递归：在实现的时候，使用递归的书写方式，可以减少代码的行数。
5. 思想中具有分治的思想：归并是分治+归并，而这个算法对于归并没有那么强的要求（主要是指代码上的直接体现），那么手撸代码的时间上可以快一些。
6. 代码真的很简洁。。。。

/**
 * 快速排序
 * 个人愿称它为排序中最强（狗头，概念理解容易，代码相对简洁，效率也很不错）
 *
 * @param arr
 */
public void quickSort(int[] arr) {
    quickSort(arr, 0, arr.length - 1);
}

public void quickSort(int[] arr, int leftIndex, int rightIndex) {
    int l = leftIndex;
    int r = rightIndex;
    if (l >= r) {
        return;
    }
    int key = arr[l];
    while (l < r) {
        while (r > l && arr[r] >= key) {
            r--;
        }
        arr[l] = arr[r];
        while (l < r && arr[l] <= key) {
            l++;
        }
        arr[r] = arr[l];
    }
    arr[l] = key;
    //printArr(arr);
    quickSort(arr, leftIndex, l);
    quickSort(arr, l + 1, rightIndex);
}

在代码实现上，关于key值的选择有各种不同，之前看到过一次左神关于快排的讲解，唯一记得就是开始（算法第一选择的key）好像是选择的最后一个数，好像是可以减少交换的次数还是怎样的，感兴趣的可以找一找。但是自己还是熟悉自己最开始理解的方式。

插入排序

关键点是：从开始算起，到任何一个数的时候，那么该数前面的数据都已经有序，因此将该数插入到它再排序中的位置，而比这个数大的都需要进行向后移动一位，因此有着【arr[j]=arr[j-1]】到最后【arr[j-2]=temp】的操作，这就是一趟插入，只是随着排序越到后面，当遇到较小的数据的时候，那么移动的数据会很多。【最坏的情况是讲一个降序的数组 使用插入排序 成为一个升序的数组】。

/**
 * 插入排序
 *
 * @param arr
 */
public void insertSort(int[] arr) {
    int len = arr.length;
    for (int i = 1; i < len; i++) {
        int temp = arr[i];
        int index = i;
        for (int j = i; j > 0; j--) {
            if (arr[j - 1] > temp) {
                arr[j] = arr[j - 1];
                index = j - 1;
            }
        }
        arr[index] = temp;
    }
}

因此代码中的关键点是：

1. 记录下当前的值。
2. 移动完成之后，将当前的值放到对应的位置。

希尔排序

我自己使用得不多，不管是在哪一种地方，都没有使用多少。嗯，又是一个分治归并思想的算法吧。

嗯嗯，不想记，不想理解，不想多写。

/**
 * 希尔排序
 *
 * @param arr
 */
public void shellSort(int[] arr) {
    int gap = 1;
    while (gap < arr.length) {
        gap = gap * 3 + 1;
    }
    while (gap > 0) {
        for (int i = gap; i < arr.length; i++) {
            int tmp = arr[i];
            int j = i - gap;
            while (j >= 0 && arr[j] > tmp) {
                arr[j + gap] = arr[j];
                j -= gap;
            }
            arr[j + gap] = tmp;
        }
        gap /= 3;
    }
}

归并排序

分治与归并的结合。重点是将每次排序结果进行归并，因此最重要的是归并函数。

好像也用到的不是很多，但是这个思想很重要，很多时候都要用到分治再归并的方式解决问题。

/**
 * 归并排序
 *
 * @param arr
 */
public void mergeSort(int[] arr) {
    mergeSort(arr, 0, arr.length - 1);
}
public void mergeSort(int[] arr, int leftIndex, int rightIndex) {
    int l = leftIndex;
    int r = rightIndex;
    if (l >= r) {
        return;
    }
    int m = l + (r - l) / 2;//可以防止越界
    mergeSort(arr, l, m);
    mergeSort(arr, m + 1, r);
    mergeArr(arr, l, m, r);
}
//归并函数
public void mergeArr(int[] arr, int leftIndex, int midIndex, int rightIndex) {
    int len = rightIndex - leftIndex + 1;
    int[] arrTemp = new int[len];
    int l = leftIndex, m = midIndex, r = rightIndex;
    int k = 0;
    int i = l, j = m + 1;
    while (i <= m && j <= r) {
        if (arr[i] < arr[j]) {
            arrTemp[k++] = arr[i++];
        } else {
            arrTemp[k++] = arr[j++];
        }
    }
    while (i <= m) {
        arrTemp[k++] = arr[i++];
    }
    while (j <= r) {
        arrTemp[k++] = arr[j++];
    }
    for (int t = 0; t < arrTemp.length; t++) {
        arr[leftIndex + t] = arrTemp[t];
    }
}

堆排序

其思想是完全二叉树树，在数组中，父节点与左右孩子节点之间的下标之间存在如下关系：父节点下标为【i】，那么左孩子下节点标为【2*i+1】，右孩子节点下标为【2*i+2】。

在排序之前第一步是需要建堆，根据需求建立大顶堆或者建立小顶堆，大顶堆用于升序排序，小顶堆用于降序排序；因为在排序的时候，将堆顶元素放于数组的最后一个位置，然后调节堆，然后再进行排序。

而堆的要求则是：如果是大顶堆，那么父节点的值要大于或等于左右孩子节点的值；如果是小顶堆，那么父节点的值要小于或等于左右孩子节点的值。

/**
 * 堆排序
 * 1. 建堆——大堆或小堆，大堆升序（规范化中，是将堆顶元素与堆尾元素进行交换，那么最大元素就去了数组尾部），小堆降序
 * 2. 将堆规范化
 *
 * @param arr
 */
public void heapSort(int[] arr) {
    int len = arr.length;

    //大顶堆 升序
    buildMaxHeap(arr, len);
    for (int i = len - 1; i >= 0; i--) {
        swap(arr, 0, i);
        len--;//最后一个元素放置好之后就不再对该元素在堆中进行调整
        heapify(arr, 0, len);
    }

    //小顶堆 降序
    //buildMinHeap(arr, len);
    ////printArr(arr);
    //for (int i = len - 1; i >= 0; i--) {
    //    swap(arr, 0, i);
    //    len--;
    //    heapifyMin(arr, 0, len);
    //}
}

//建大堆
public void buildMaxHeap(int[] arr, int len) {
    for (int i = len / 2; i >= 0; i--) {
        heapify(arr, i, len);
    }
}

//建小堆
public void buildMinHeap(int[] arr, int len) {
    for (int i = len / 2; i >= 0; i--) {
        heapifyMin(arr, i, len);
    }
}

//用于建大堆
public void heapify(int[] arr, int i, int len) {
    //以i节点为根节点，求i节点的左右孩子节点
    int l = 2 * i + 1;
    int r = 2 * i + 2;
    int max = i;

    //建大堆的关键点
    if (l < len && arr[l] > arr[max]) {
        max = l;
    }
    if (r < len && arr[r] > arr[max]) {
        max = r;
    }
    if (max != i) {
        swap(arr, i, max);
        heapify(arr, max, len);
    }
}

//用于建小堆
public void heapifyMin(int[] arr, int i, int len) {
    //以i节点为根节点，求i节点的左右孩子节点
    int l = 2 * i + 1;
    int r = 2 * i + 2;
    int min = i;

    //建小堆的关键点
    if (l < len && arr[l] < arr[min]) {
        min = l;
    }
    if (r < len && arr[r] < arr[min]) {
        min = r;
    }
    if (min != i) {
        swap(arr, i, min);
        heapifyMin(arr, min, len);
    }
}

因此在代码的实现过程中比较麻烦。

1. 写出堆调整【heapify】函数。
2. 写出建堆【buildHeap】函数。
3. 堆排序函数，其中一直排序，一直调整堆。

嗯，以上只是根据个人对几个排序算法的理解然后写出来的一些笔记和想法，如果有不准确的地方，还望告知。