算法（四）-排序

一、排序分类

简单写下如下4种排序：

排序算法	平均时间复杂度	空间复杂度	稳定性
冒泡排序	O(n2)	O(1)	稳定
选择排序	O(n2)	O(1)	不稳定
插入排序	O(n2)	O(1)	稳定
快速排序	O(nlogn)	O(logn)	不稳定

二、排序介绍

2.1 冒泡排序

思路：比较相邻的元素。如果第一个比第二个大，就交换他们两个。每轮冒泡出一个最大或者最小元素出来。

public static int[] bubbleSort(int[] arr) {
   for (int i = 0; i < arr.length; i++) {
       for (int j = i + 1; j < arr.length; j++) {
           if (arr[i] > arr[j]) {
               int tmp = arr[i];
               arr[i] = arr[j];
               arr[j] = tmp;
           }
       }
   }
   return arr;
}

冒泡排序

2.2选择排序

思路：第一轮找到最小元素，与0号元素互换，第二轮找到第二小元素与1号元素互换，以此类推

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

选择排序

2.3 插入排序

思路：遍历数组，后面的每一位都与前面已排序的数组进行扫描比较，确定对应的顺序位置并插入，其余元素均往后移1位。

public static int[] insertSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int cur = arr[i];
        int j;
        for (j = i-1; j >= 0; j--) { //与之前的每一个数比较
           if(cur < arr[j]){
               arr[j+1] = arr[j];//比较之后立即移动位置
           }else {
               break;
           }
        }
        //插入属于到对应位置（这里因为做了j--，所以需要+1加回来）
        arr[j+1] = cur;
    }
    return arr;
}

插入排序

2.4 快速排序

思路：分治 + 递归
先从数列中取出一个数作为key值，左右两边指针往中间走，左边找出比基准大的数，右边找出比基准小的数，两者交换。如果左右指针相交，则该位置值与基准位置交换值。然后再依次递归当前基准位置的左边部分和右边部分。最终每个小数列有序，拼成一整个有序数列。

    public static void quickSort(int[] arr, int low, int high) {
        if (low > high) {
            return;
        }
        int i = low;
        int j = high;
        int key = arr[low];

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

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

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

        //最后将基准位置与i和j重叠的位置交换
        arr[low] = arr[i];
        arr[i] = key;

        //递归调用左半边数组
        quickSort(arr, low, j - 1);
        //递归调用右半边数组
        quickSort(arr, j + 1, high);
    }

快速排序

未完待续...

动图出处：
https://www.jianshu.com/p/c4217456c224