五、排序

1、常见的排序算法
2、算法的时间复杂度
- 时间频度和时间复杂度
- 常见的时间复杂度
3、排序算法的时间复杂度
- 空间复杂度
4、冒泡排序
5、选择排序
6、插入排序
7、希尔排序
8、快速排序
9、归并排序
10、基数排序
11、堆排序
12、八大排序算法的对比

1、常见的排序算法

2、算法的时间复杂度

时间频度和时间复杂度

时间频度T(n)
一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。
时间复杂度O(n)
一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T（n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。
在T(n)=4n²-2n+2中，就有f(n)=n²，使得T（n)/f(n)的极限值为4，那么O(f(n))，也就是时间复杂度为O(n²)

对于不是只有常数的时间复杂度忽略时间频度的系数、低次项、常数
对于只有常数的时间复杂度，将常数看为1
常见的时间复杂度
常数阶 O(1)
int i = 1;
i++;
无论代码执行了多少行，只要没有循环等复杂的结构，时间复杂度都是O(1)
对数阶O(log2n)
while(i i = i*2;
}
此处i并不是依次递增到n，而是每次都以倍数增长。假设循环了x次后i大于n。则2x = n，x=log2n
线性阶O(n)
for(int i = 0; i i++;
}
这其中，循环体中的代码会执行n+1次，时间复杂度为O(n)
线性对数阶O(nlog2n)
for(int i = 0; i j = 1;
while(j j = j*2;
}
}
此处外部为一个循环，循环了n次。内部也是一个循环，但内部f循环的时间复杂度是log2n
所以总体的时间复杂度为线性对数阶O(nlog2n)
平方阶O(n2)
for(int i = 0; i for(int j = 0; j //循环体
}
}
立方阶O(n3)
for(int i = 0; ifor(int j = 0; jfor(int k = 0; k //循环体
}
}
}
可以看出平方阶、立方阶的复杂度主要是否循环嵌套了几层来决定的
3、排序算法的时间复杂度

排序算法	平均时间	最差时间	稳定性	空间复杂度	备注
冒泡排序	O(n2)	O(n2)	稳定	O(1)	n较小时好
交换排序	O(n2)	O(n2)	不稳定	O(1)	n较小时好
选择排序	O(n2)	O(n2)	不稳定	O(1)	n较小时好
插入排序	O(n2)	O(n2)	稳定	O(1)	大部分已有序时好
基数排序	O(n*k)	O(n*k)	稳定	O(n)	二维数组（桶）、一维数组（桶中首元素的位置）
希尔排序	O(nlogn)	O(ns)(1<s<2)	不稳定	O(1)	s是所选分组
快速排序	O(nlogn)	O(n2)	不稳定	O(logn)	n较大时好
归并排序	O(nlogn)	O(nlogn)	稳定	O(1)	n较大时好
堆排序	O(nlogn)	O(nlogn)	不稳定	O(1)	n较大时好

空间复杂度

4、冒泡排序

算法步骤

比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
一共进行了数组元素个数-1次大循环，且每次大循环中需要比较的元素越来越少。
优化：如果在某次大循环，发现没有发生交换，则证明已经有序。

代码

public class BubbleSort {
    public static void main(String[] args) {
//        int arr[] = {3, 9, -1, 10, 20};
//        
//        System.out.println("排序前");
//        System.out.println(Arrays.toString(arr));
        //为了容量理解，我们把冒泡排序的演变过程，给大家展示
        //测试一下冒泡排序的速度O(n^2), 给80000个数据，测试
        //创建要给80000个的随机的数组
        int[] arr = new int[80000];
        for(int i =0; i < 80000;i++) {
            arr[i] = (int)(Math.random() * 8000000); //生成一个[0, 8000000) 数
        }
        Date data1 = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String date1Str = simpleDateFormat.format(data1);
        System.out.println("排序前的时间是=" + date1Str);
        //测试冒泡排序
        bubbleSort(arr);
        Date data2 = new Date();
        String date2Str = simpleDateFormat.format(data2);
        System.out.println("排序后的时间是=" + date2Str);
    }
// 将前面额冒泡排序算法，封装成一个方法
    public static void bubbleSort(int[] arr) {
        // 冒泡排序 的时间复杂度 O(n^2), 自己写出
        int temp = 0; // 临时变量
        boolean flag = false; // 标识变量，表示是否进行过交换
        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]) {
                    flag = true;
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
            //System.out.println("第" + (i + 1) + "趟排序后的数组");
            //System.out.println(Arrays.toString(arr));
            if (!flag) { // 在一趟排序中，一次交换都没有发生过
                break;
            } else {
                flag = false; // 重置flag!!!, 进行下次判断
            }
        }
    }
}

5、选择排序

算法步骤

遍历整个数组，找到最小（大）的元素，放到数组的起始位置。
再遍历剩下的数组，找到剩下元素中的最小（大）元素，放到数组的第二个位置。
重复以上步骤，直到排序完成。
一共需要遍历数组元素个数-1次，当找到第二大（小）的元素时，可以停止。这时最后一个元素必是最大（小）元素。

选择排序时间复杂度O(n^2)，比冒泡排序快
代码

public class SelectSort {
    public static void main(String[] args) {
        int[] arr = {101, 34, 119, 1, -1, 90, 123};
        selectSort(arr);
    }
    public static void selectSort(int[] arr ){
        for (int i = 0; i < arr.length - 1; i++) {
            int min = arr[i];
            int minIndex = i;
            for (int j = i + 1; j < arr.length ; j++) {
                if (min > arr[j]){// 说明假定的最小值，并不是最小
                    min = arr[j];//重置最小值
                    minIndex = j;//重置minIndex
                }
            }
            // 将最小值，放在arr[i], 即交换
            if (minIndex != i){
                arr[minIndex] = arr[i];
                arr[i] = min;
            }
        }
        for (int i:arr){
            System.out.print(i + "\t");
        }
    }
}

6、插入排序

算法步骤

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

时间复杂度O(n^2)

代码

public class InsertSort {
    public static void main(String[] args) {
//        int[] arr = {101, 34, 119, 1, -1, 89};
//        insertSort(arr);
        int[] arr = new int[80000];
        for (int i = 0; i < 80000; i++) {
            arr[i] = (int) (Math.random() * 80000); // 生成一个[0, 8000000) 数
        }
        System.out.println("插入排序前");
        Date data1 = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String date1Str = simpleDateFormat.format(data1);
        System.out.println("排序前的时间是=" + date1Str);
        insertSort(arr); //调用插入排序算法
        Date data2 = new Date();
        String date2Str = simpleDateFormat.format(data2);
        System.out.println("排序前的时间是=" + date2Str);
    }
    public static void  insertSort(int[] arr){
        int insertVal = 0;
        int inserIndex = 0;
        for (int i = 1; i < arr.length; i++) {
            insertVal = arr[i];//定义待插入的数v
            inserIndex = i-1;// 即arr[1]的前面这个数的下标
            // 给insertVal 找到插入的位置
            // 说明
            // 1. insertIndex >= 0 保证在给insertVal 找插入位置，不越界
            // 2. insertVal < arr[insertIndex] 待插入的数，还没有找到插入位置
            // 3. 就需要将 arr[insertIndex] 后移
            while (inserIndex >= 0 && insertVal < arr[inserIndex]){
                arr[inserIndex + 1] = arr[inserIndex];
                inserIndex--;
            }
            // 当退出while循环时，说明插入的位置找到, insertIndex + 1
            //这里我们判断是否需要赋值
            if (inserIndex + 1 != i) {
                arr[inserIndex + 1] = insertVal;
            }
        }
//        for (int i:arr){
//            System.out.print(i + "\t");
//        }
    }

7、希尔排序

回顾：插入排序存在的问题
当最后一个元素为整个数组的最小元素时，需要将前面的有序数组中的每个元素都向后移一位，这样是非常花时间的。
所以有了希尔排序来帮我们将数组从无序变为整体有序再变为有序。
算法步骤

选择一个增量序列t1（一般是数组长度/2），t2（一般是一个分组长度/2），……，tk，其中 ti > tj, tk = 1；
按增量序列个数 k，对序列进行 k 趟排序；
每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

示意图

代码

public class ShellSort {
    public static void main(String[] args) {
//        int[] arr = { 8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
//        shellSort(arr);
        // 创建要给80000个的随机的数组
        int[] arr = new int[80000];
        for (int i = 0; i < 80000; i++) {
            arr[i] = (int) (Math.random() * 80000); // 生成一个[0, 8000000) 数
        }
        System.out.println("排序前");
        Date data1 = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String date1Str = simpleDateFormat.format(data1);
        System.out.println("排序前的时间是=" + date1Str);
        //shellSort(arr); //交换式 耗时较长
        shellSort2(arr);//移位方式 耗时短，更高效
        Date data2 = new Date();
        String date2Str = simpleDateFormat.format(data2);
        System.out.println("排序前的时间是=" + date2Str);
    }
    //使用逐步推导的方式来编写希尔排序
    // 希尔排序时， 对有序序列在插入时采用交换法,
    // 思路(算法) ===> 代码
    public static void shellSort(int[] arr ){
        int temp = 0;
        for (int gap = arr.length/2; gap > 0; gap/=2) {
            for (int i = gap; i < arr.length ; i++) {
                for (int j = i - gap; j >= 0 ; j -= gap) {
                    if (arr[j] > arr[j + gap]){
                        temp = arr[j];
                        arr[j] = arr[j + gap];
                        arr[j + gap] = temp;
                    }
                }
            }
        }
//        for (int i:arr){
//            System.out.print(i + "\t");
//        }
    }
    //对交换式的希尔排序进行优化->移位法
    public static void shellSort2(int[] arr ) {
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                int j = i;
                int temp = arr[j];
                if (arr[j] < arr[j - gap]){
                    while(j - gap >= 0 && temp < arr[j - gap] ){
                        //移动
                        arr[j] = arr[j - gap];
                        j -= gap;
                    }
                    //当退出while后，就给temp找到插入的位置
                    arr[j] = temp;
                }
            }
        }
    }
}

8、快速排序

算法步骤

从数列中挑出一个元素，称为 “基准”（pivot）;
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

代码

public class QuickSort {
    public static void main(String[] args) {
//        int[] arr = {-9,78,0,23,-567,70, -1,900, 4561};
//        quickSort(arr,0, arr.length-1);
//        for (int i:arr){
//            System.out.print(i + "\t");
//        }
        //测试快排的执行速度
        // 创建要给80000个的随机的数组
        int[] arr = new int[8000000];
        for (int i = 0; i < 8000000; i++) {
            arr[i] = (int) (Math.random() * 80000); // 生成一个[0, 8000000) 数
        }
        System.out.println("排序前");
        Date data1 = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String date1Str = simpleDateFormat.format(data1);
        System.out.println("排序前的时间是=" + date1Str);
        quickSort(arr, 0, arr.length-1);
        Date data2 = new Date();
        String date2Str = simpleDateFormat.format(data2);
        System.out.println("排序前的时间是=" + date2Str);
        //System.out.println("arr=" + Arrays.toString(arr));
    }
    public static void quickSort(int[] arr,int left,int right){
        int l = left;//左下标
        int r = right;//右下标
        //pivot 中轴值
        int pivot = arr[(left + right) / 2];
        int temp = 0; //临时变量，作为交换时使用
        //while循环的目的是让比pivot 值小放到左边
        //比pivot 值大放到右边
        while (l < r){
            //在pivot的左边一直找,找到大于等于pivot值,才退出
            while (arr[l] < pivot){
                l += 1;
            }
            //在pivot的右边一直找,找到小于等于pivot值,才退出
            while (arr[r] > pivot){
                r -= 1;
            }
            //如果l >= r说明pivot 的左右两的值，已经按照左边全部是
            //小于等于pivot值，右边全部是大于等于pivot值
            if (l >= r){
                break;
            }
            //交换
            temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;
            //如果交换完后，发现这个arr[l] == pivot值 相等 r--， 前移
            if (arr[l] == pivot){
                r -= 1;
            }
            //如果交换完后，发现这个arr[r] == pivot值 相等 l++， 后移
            if (arr[r] == pivot){
                l += 1;
            }
        }
        // 如果 l == r, 必须l++, r--, 否则为出现栈溢出
        if (l == r) {
            l += 1;
            r -= 1;
        }
        //向左递归
        if(left < r) {
            quickSort(arr, left, r);
        }
        //向右递归
        if(right > l) {
            quickSort(arr, l, right);
        }
    }
}

9、归并排序

算法步骤
归并排序用到了分而治之的思想，其难点是治

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
设定两个指针，最初位置分别为两个已经排序序列的起始位置
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
重复上一步直到某一指针达到序列尾
将另一序列剩下的所有元素直接复制到合并序列尾

此时第二个序列的指针已经到达末尾，则将第一个序列中剩下的元素全部放入和合并序列末尾

代码

public class MergeSort {
    public static void main(String[] args) {
//        int arr[] = { 8, 4, 5, 7, 1, 3, 6, 2 };
//        int[] temp = new int[arr.length];
//        mergeSort(arr,0,arr.length-1,temp);
//        for (int i:arr){
//            System.out.print(i + "\t");
//        }
        //测试快排的执行速度
        // 创建要给80000个的随机的数组
        int[] arr = new int[8000000];
        for (int i = 0; i < 8000000; i++) {
            arr[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000) 数
        }
        System.out.println("排序前");
        Date data1 = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String date1Str = simpleDateFormat.format(data1);
        System.out.println("排序前的时间是=" + date1Str);
        int temp[] = new int[arr.length]; //归并排序需要一个额外空间
        mergeSort(arr, 0, arr.length - 1, temp);
        Date data2 = new Date();
        String date2Str = simpleDateFormat.format(data2);
        System.out.println("排序前的时间是=" + date2Str);
    }
    public static void mergeSort(int[] arr,int left,int right,int[] temp){
        if(left < right){
            int mid = (left + right) / 2; //中间索引
            //向左递归进行分解
            mergeSort(arr,left,mid,temp);
            //向右递归进行分解
            mergeSort(arr,mid + 1,right,temp);
            //合并
            merge(arr,left,mid,right,temp);
        }
    }
    //合并的方法
    public static void merge(int[] arr,int left,int mid,int right,int[] temp){
        int i = left; // 初始化i, 左边有序序列的初始索引
        int j = mid + 1; //初始化j, 右边有序序列的初始索引
        int t = 0; // 指向temp数组的当前索引
        //(一)
        //先把左右两边(有序)的数据按照规则填充到temp数组
        //直到左右两边的有序序列，有一边处理完毕为止
        while(i <= mid && j <= right){//继续
            //如果左边的有序序列的当前元素，小于等于右边有序序列的当前元素
            //即将左边的当前元素，填充到 temp数组
            //然后 t++, i++
            if(arr[i] <= arr[j]){
                temp[t] = arr[i];
                t++;
                i++;
            }else {//反之,将右边有序序列的当前元素，填充到temp数组
                temp[t] = arr[j];
                t++;
                j++;
            }
        }
        //(二)
        //把有剩余数据的一边的数据依次全部填充到temp
        while (i <= mid){//左边的有序序列还有剩余的元素，就全部填充到temp
            temp[t] = arr[i];
            t++;
            i++;
        }
        while(j <= right){
            temp[t] = arr[j];
            t++;
            j++;
        }
        //(三)
        //将temp数组的元素拷贝到arr
        //注意，并不是每次都拷贝所有
        t = 0;
        int templeft = left;
        //第一次合并 tempLeft = 0 , right = 1 //  tempLeft = 2  right = 3 // tL=0 ri=3
        //最后一次 tempLeft = 0  right = 7
        while(templeft <= right){
            arr[templeft] = temp[t];
            t++;
            templeft++;
        }
    }
}

10、基数排序

算法步骤

将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零
从最低位开始，依次进行一次排序
从最低位排序一直到最高位（个位->十位->百位->…->最高位）排序完成以后, 数列就变成一个有序序列
需要我们获得最大数的位数
- 可以通过将最大数变为String类型，再求得它的长度即可

按照个位，放到对应的桶中

依次取出，同一个桶中有多个元素的，先放入的先取出

再按照十位，放到对应的桶中，个位数前面补0

再依次取出桶中元素

再按照百位，放到对应的桶中，个位数和十位数前面补0

再依次取出桶中元素
再按照千位，放到对应的桶中，个位数、十位数和百位数前面补0
当所有的数都在0号桶时，依次取出元素，这时顺序即为排好后的顺序

稳定排序 : 如果要排序的数组有两个相同的数字如a1 =a2 =1 {a1,2,3,a2} 排序后 {a1,a2,2,3} a1还是在a2的前面

代码

public class RadixSort {
    public static void main(String[] args) {
//        int arr[] = { 53, 3, 542, 748, 14, 214};
//        radixSort(arr);
//        for (int i:arr){
//            System.out.print(i + "\t");
//        }
        // 80000000 * 11 * 4 / 1024 / 1024 / 1024 =3.3G
        int[] arr = new int[8000000];
        for (int i = 0; i < 8000000; i++) {
            arr[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000) 数
        }
        System.out.println("排序前");
        Date data1 = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String date1Str = simpleDateFormat.format(data1);
        System.out.println("排序前的时间是=" + date1Str);
        radixSort(arr);
        Date data2 = new Date();
        String date2Str = simpleDateFormat.format(data2);
        System.out.println("排序前的时间是=" + date2Str);
        //System.out.println("基数排序后 " + Arrays.toString(arr));
    }
    public static void radixSort(int[] arr){
        //1. 得到数组中最大的数的位数
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (max < arr[i]){
                max = arr[i];
            }
        }
        //得到最大数是几位数
        int maxlength = (max + "").length();
        //定义一个二维数组，表示10个桶, 每个桶就是一个一维数组
        //说明
        //1. 二维数组包含10个一维数组
        //2. 为了防止在放入数的时候，数据溢出，则每个一维数组(桶)，大小定为arr.length
        //3. 名明确，基数排序是使用空间换时间的经典算法
        int[][] bucket = new int[10][arr.length];
        //为了记录每个桶中，实际存放了多少个数据,我们定义一个一维数组来记录各个桶的每次放入的数据个数
        //可以这里理解
        //比如：bucketElementCounts[0] , 记录的就是  bucket[0] 桶的放入数据个数
        int[] bucketElementCounts = new int[10];
        for (int i = 0, n = 1; i < maxlength; i++,n*=10) {
            //(针对每个元素的对应位进行排序处理)， 第一次是个位，第二次是十位，第三次是百位..
            for (int j = 0; j < arr.length; j++) {
                //取出每个元素的对应位的值
                int digtalOfElement = arr[j] / n % 10;
                //放入到对应的桶中
                bucket[digtalOfElement][bucketElementCounts[digtalOfElement]] = arr[j];
                bucketElementCounts[digtalOfElement]++;
            }
            //按照这个桶的顺序(一维数组的下标依次取出数据，放入原来数组)
            int index = 0;
            //遍历每一桶，并将桶中是数据，放入到原数组
            for (int k = 0; k < bucket.length; k++) {
                //如果桶中，有数据，我们才放入到原数组
                if (bucketElementCounts[k] != 0){
                    //循环该桶即第k个桶(即第k个一维数组), 放入
                    for (int l = 0; l < bucketElementCounts[k]; l++) {
                        //取出元素放入到arr
                        arr[index] = bucket[k][l];
                        index++;
                    }
                }
                //第i+1轮处理后，需要将每个 bucketElementCounts[k] = 0 ！！！！
                bucketElementCounts[k] = 0;
            }
        }
    }
}

11、堆排序

基本介绍

堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为 O(nlogn)，它也是不稳定排序
堆是具有以下性质的完全二叉树：
- 每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆
  - 注意 : 没有要求结点的左孩子的值和右孩子的值的大小关系
- 每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆
一般升序排序采用大顶堆，降序排列使用小顶堆

排序思路

堆是一种树结构，但是排序中会将堆进行顺序存储（变为数组结构）
将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆
将堆顶元素与末尾元素交换，将最大元素”沉”到数组末端
重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序

实现代码

/**
 * @author Chen Panwen
 * @data 2020/7/27 16:19
 */
public class Demo2 {
   public static void main(String[] args) {
      int[] arr = {4, 6, 8, 5, 9};
      //堆排序
      heapSort(arr);
      System.out.println("堆排序后结果");
      System.out.println(Arrays.toString(arr));
   }
   /**
    * 堆排序（升序排序）
    * @param arr 待排序数组
    */
   public static void heapSort(int[] arr) {
      for(int i=arr.length-1; i>=0; i--) {
         //将数组调整为大顶堆，长度为未排序数组的长度
         for(int j=arr.length/2-1; j>=0; j--) {
            adjustHeap(arr, j, i+1);
         }
         //调整后，数组首元素就为最大值，与为元素交换
         int temp = arr[i];
         arr[i] = arr[0];
         arr[0] = temp;
      }
   }
   /**
    * 将无序数组进行调整，将其调整为大顶堆
    * @param arr 待调整的数组
    * @param index 非叶子节点的索引
    * @param length 待调整数组的长度
    */
   public static void adjustHeap(int[] arr, int index, int length) {
      //保存非叶子节点的值，最后需要进行交换操作
      int temp = arr[index];
      //进行调整操作
      //index*2+1代表其左子树
      for(int i = index*2+1; i<length; i = i*2+1) {
         //如果存在右子树，且右子树的值大于左子树，就让索引指向其右子树
         if(i+1<length && arr[i] < arr[i+1]) {
            i++;
         }
         //如果右子树的值大于该节点的值就交换，同时改变索引index的值
         if(arr[i] > arr[index]) {
            arr[index] = arr[i];
            index = i;
         }else {
            break;
         }
         //调整完成后，将temp放到最终调整后的位置
         arr[index] = temp;
      }
   }
}

1、常见的排序算法

2、算法的时间复杂度

时间频度和时间复杂度

常见的时间复杂度

常数阶 O(1)

对数阶O(log2n)

线性阶O(n)

线性对数阶O(nlog2n)

平方阶O(n2)

立方阶O(n3)

3、排序算法的时间复杂度

空间复杂度

4、冒泡排序

5、选择排序

6、插入排序

7、希尔排序

8、快速排序

9、归并排序

10、基数排序

11、堆排序

12、八大排序算法的对比