1.前言

• 这篇文章讲解的是Java中或者面试中常用的排序算法。
• 文章中实例 [linhaojian的Github](https://github.com/linhaojian

---

2.复杂度

复杂度.png

• 相关概率

稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
O(N) : for(int i=0;i<10:i++){}；
O(N*N) : for(int i=0;i<10:i++){for(int i=0;i<10:i++){}}；
O(log2n) : 就是将循环次数/2；
O(nlog2n) : 就是循环数据的次数1分为2；
空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。

---

3.排序算法

3.1 冒泡

• 描述：
  1.比较集合相邻2个元素，如果前者大于后者交换他们的位置。这一点会得出最大的元素 & 放置在集合最后
  2.持续对剩下的元素进行1的操作。

• 演示：

  
  冒泡排序.gif
• 代码：

 public static void bubbleSort(int[] numbers)
    {
        int temp = 0;
        int size = numbers.length;
        for(int i = 0 ; i < size-1; i ++)
        {
            for(int j = 0 ;j < size-1-i ; j++)
            {
                if(numbers[j] > numbers[j+1])  //交换两数位置
                {
                    temp = numbers[j];
                    numbers[j] = numbers[j+1];
                    numbers[j+1] = temp;
//                    System.out.println(Arrays.toString(numbers));
                }
            }
//            System.out.println("------------");
        }
    }

3.2 选择

• 描述：
  1.在未排序序列中找到最小元素，存放到排序序列的起始位置
  2.再从剩余未排序元素中继续寻找最小元素，然后放到排序序列起始位置。
  3.以此类推，直到所有元素均排序完毕。

• 演示：

  
  选择排序.gif
• 代码：

    public static void selectSort(int[] numbers) {
        int size = numbers.length;
        int temp;
        //从零开始向后遍历集合
        for (int i = 0; i < size; i++) {
            //将 i 赋值给k
            int k = i;
            //从集合最后一位开始向前遍历
            for (int j = size - 1; j>i; j--)  {
                //记录比较之后值小的位置
                if (numbers[j] < numbers[k]) {
                    k = j;
                }
            }
            // 将找出最小值与i位置的值交互，把最小值放置在集合最前
            temp = numbers[i];
            numbers[i] = numbers[k];
            numbers[k] = temp;
//            System.out.println(Arrays.toString(array));
        }
    }

3.3 插入

• 描述：
  1.从第一个元素开始，该元素可以认为已经被排序；
  2.取出下一个元素，在已经排序的元素序列中从后向前扫描；
  3.如果该元素（已排序）大于新元素，将该元素移到下一位置；
  4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
  5.将新元素插入到该位置后；
  6.重复步骤2~5。

• 演示：

  
  插入排序.gif
• 代码：

private static void insertSort(int[] numbers) {
        //从1开始递增的遍历数据
        for (int i = 1; i < numbers.length; i++) {
            // 将 i 对应的值 赋予给 temp
            int temp = numbers[i];
            int j;
            // 从 i-1 开始递减的遍历
            for (j = i - 1; j >= 0; j--) {
                //判断temp 是否小于当前j位置的值
                if (temp < numbers[j]) {
                    numbers[j + 1] = numbers[j];
                    System.out.println(Arrays.toString(numbers));
                } else {
                    break;
                }
            }
            numbers[j + 1] = temp;
            System.out.println(j+"  "+Arrays.toString(numbers));
        }
    }

3.4 快速

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

    public static void quickSortHelp(int[] arr) {
        arr = new int[]{5,3,2,1,4,8,7,9};
        quickSort(arr,0, arr.length-1);
    }
    public static void quickSort(int[] arr,int low, int high) {
        if(low<high) {
            int partition = partition(arr,low,high);
            System.out.println("partition : "+partition+"  low : "+low+"  high : "+high+"  arr : "+Arrays.toString(arr));
            quickSort(arr,low, partition-1);
            quickSort(arr,partition+1, high);
        }
    }
    public static int partition(int[] arr,int low,int high) {
        int base = arr[low]; //用子表的第一个记录做枢轴(分水岭)记录
        System.out.println("base : "+base);
        while(low<high) {
            while(arr[high]>=base&&low<high){
                high--;
            }
            Swap(arr,high,low);
            System.out.println("[high:"+high+"] "+Arrays.toString(arr));
            while(arr[low]<=base&&low<high) {
                low++;
            }
            Swap(arr,high,low);
            System.out.println("[low:"+low+"] "+Arrays.toString(arr));
        }
        System.out.println(Arrays.toString(arr));
        System.out.println("----------------------------");
        return low;
    }
    public static void Swap(int[] arr,int high,int low) {
        int temp = arr[low];
        arr[low] =arr[high];
        arr[high] = temp;
    }

---

4.总结

• 到此，常用的排序算法讲解完毕。
• 如果喜欢我的分享，可以点击 关注 或者 赞，你们支持是我分享的最大动力 。
• linhaojian的Github

欢迎关注linhaojian_CSDN博客或者linhaojian_简书！

不定期分享关于安卓开发的干货。

---

写技术文章初心

• 技术知识积累
• 技术知识巩固
• 技术知识分享
• 技术知识交流