选择排序

选择排序的原理十分简单直观，通常使用两层 for 循环来实现：第一层 for 循环依次选定数组从 0 到 N 的每一个索引位置的值，第二层 for 循环将该索引后的每个值依次与该索引的值进行比较，将较小值交换到第一层循环索引所在的位置。这就使得第一层 for 每一次循环都是在将剩余数组的最小值排列在剩余数组的最前列，最终实现升序排列。
时间复杂度为 O(N^2)

选择排序的图形化排序过程：



选择排序代码实现：

public void selectSort(int[] arr) {
	//第一层for循环的arr[i]每次循环之后都会填入i之后的位置的最小值
   for (int i = 0; i < arr.length - 1; i++) {//有序区
   		//将arr[i]之后每一个值依次与arr[i]比较，若较小则交换，保证arr[i]的值最小
       for (int j = i + 1; j < arr.length; j++) {//无序区
           if (arr[i] > arr[j]) {
               int temp = arr[i];
               arr[i] = arr[j];
               arr[j] = temp;
           }
       }
   }
｝

创建一个长度为10万的随机数数组，测试5次选择排序花费的时间如下：

冒泡排序

冒泡排序同样使用双层 for 循环，第二层循环从 0 到 N 将相邻索引位置的值两两对比，将较大值交换到后一位，第二层循环遍历完成，就将无序区的最大值推到了数组最后。第一层循环重复冒泡过程，将无序区的最大值依次交换到数组右边的有序区，最终实现升序排列。
时间复杂度为 O(N^2)

冒泡排序的图形化排序过程：



冒泡排序代码实现：

public static void bubbleSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
    	//将无序区的最大值移动到最右的有序区
        for (int j = 0; j < arr.length - 1 - i; j++) {
        	//如果左边的值大于右边的值，则互换位置
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

创建一个长度为10万的随机数数组，测试5次冒泡排序花费的时间如下：

插入排序

插入排序的原理是将数组中索引 0 既定为有序区，然后把索引 1 的值取出设定为插入值，将插入值和索引 0 的值对比，如果索引 0 的值较大，则把索引 0 的值往后移动一位，插入值到空出的位置，则索引 0 和索引 1 就是有序的。接着把索引 2 的值作为插入值依次往前对比，如果前面的值较大，则该值往后移动一位，直到找到一个更小值，将插入值放置到更小值之后，又形成了一个有序区。以此类推，最终整个数组都变成有序。
时间复杂度为 O(N^2)

插入排序的图形化排序过程：



插入排序代码实现：

public static void insertSort(int[] arr) {
   // j:插入位置的指针,insertNote:要插入的数据
    int j, insertNote;

    // 从数组的第二个元素开始循环将数组中的元素插入
    for (int i = 1; i < arr.length; i++) {
        // 设置数组中的第2个元素为第一次循环要插入的数据
        insertNote = arr[i];
        j = i - 1;
        while (j >= 0 && insertNote < arr[j]) {
            // 如果要插入的元素小于第j个元素,就将第j个元素向后移动
            arr[j + 1] = arr[j];
            // 将j-1,开始判断前一位与插入值的大小
            j--;
        }
        // 直到要插入的元素不小于第j个元素,将insertNote插入到数组中
        arr[j + 1] = insertNote;
    }
}

创建一个长度为10万的随机数数组，测试5次插入排序花费的时间如下：

快速排序

快速排序的原理是在数组中随机取一个基准数，一个最左索引 i 和一个最右索引 j 。从索引 j 开始往左找到第一个小于基准值的值，将其赋值给 arr[i] ，然后将 i 往右移动一格；接着从索引 i 开始往右找到第一个大于基准值的值，将其赋值给 arr[j] ，并把 j 往左移动一格。依此类推，当 i 和 j 索引重合时停止，最后将基准值赋值给 arr[i] ，至此 i 左边的值都比 i 小，i 右边的值都比 i 大 ，接着使用递归将左右两边的子数组分别进行快速排序，最终得到一个有序数组。
时间复杂度为 O(N*logN)

快速排序的图形化排序过程：



快速排序代码实现：

public static void quickSort(int[] arr) {
    if (arr.length == 0) return;
    quickSort(arr, 0, arr.length - 1);
}

private static void quickSort(int[] arr, int low, int high) {
    if (low >= high) return;
    //取左边的数作为基准数
    int i = low, j = high, index = arr[i];
    //i==j时跳出循环
    while (i < j) {
        //从最右开始向左寻找第一个小于index的数
        while (i < j && arr[j] >= index) j--;
        //将arr[j]放入arr[i],并将i右移
        if (i < j) arr[i++] = arr[j];
        //从最左开始向右寻找第一个大于index的数
        while (i < j && arr[i] <= index) i++;
        //将arr[i]放入arr[j],并将j左移
        if (i < j) arr[j--] = arr[i];
    }
    //最后将基数填入i
    arr[i] = index;
    //至此 , i左边都比i小 ,i右边都比i大
    quickSort(arr, low, i - 1);//递归,分治i左边
    quickSort(arr, i + 1, high);//递归,分治i右边
}

创建一个长度为10万的随机数数组，测试5次快速排序花费的时间如下：

堆排序

堆排序的原理是建立一个完全二叉树，将数组的值填入其中，然后从右往左从下往上依次调整堆结构，使父节点的值不小于其两个子节点的值，一轮调整过后，根结点的键值就是所有堆结点键值中最大者。

接着将根节点的值与最后一个叶子节点的值互换，并将得到最大值的叶子节点从二叉树中取出，置入数组的最后，然后再次调整堆结构，依次类推，最终得到一个有序数组。

时间复杂度为 O(N*logN)

堆排序的图形化排序过程：



堆排序代码实现：

 public static void heapSort(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--) {
        swap(arr, 0, j);//将堆顶元素与末尾元素进行交换
        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值放到最终的位置
}

//交换元素
public static void swap(int[] arr, int a, int b) {
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

创建一个长度为10万的随机数数组，测试5次堆排序花费的时间如下：