排序算法是最基础的算法知识,也是面试笔试中必考的问题!!!!

  • 笔试题中主要是各个算法的复杂度,稳定性,所属类型和模拟几次实现结果之类的问题
    通过本文的两张总结图10张算法动态图基本都可以迎刃而解

  • 面试题中当然就是手撕代码了,自己实现一个排序方法,如果没有较好的准备,很容易就蒙圈。虽然大家在数据结构课程都学过大部分的排序算法了,但是知道原理和手写出来还是有很大区别的。

现在我就将这十种排序算法的Java代码实现也记录在这里,方便自己复习,也方便同样在准备找工作的同学

本文图片大多数都转自这里,感谢这个大佬的图,牛批!! 如果觉得我的总结的不是很清楚可以去看看大佬的思路

下面所有的代码我都经过100000次随机数据的测试了,如果有问题请私聊我及时更正。

各类排序算法的对比与分类


选择排序

单向选择

i 记录当前有序位
j 记录遍历数组指针
minIndex 记录每次遍历的最小数的下标
每次遍历结束交换 下标为i 和下标为 minIndex 的值

/** * 选择排序1 * 每次遍历查找剩余元素的最小值然后放到对应的位置 * * @param arr */
    public static void SelectionSort1(int[] arr) {

        int n = arr.length;
        for (int i = 0; i < n; i++) {
            int minIndex = i;
            for (int j = i; j < n; j++) {
                if (arr[j] < arr[minIndex])
                    minIndex = j;
            }
            swap(arr, i, minIndex);
        }
    }
双向选择

left 记录左侧有序位(从小到大)
right 记录右侧有序位 (从大到小)
类似于单向选择从大到小的排序,双向选择是同时进行从小到大和从大到小的排序
每次遍历获取最大值和最小值并调整到正确位置

	/** * 选择排序2 * 每次遍历查找剩余元素的最小值和最大值然后放到对应的位置 * * @param arr */
    public static void SelectionSort2(int[] arr) {

        int left = 0;
        int right = arr.length - 1;

        while (left < right) {
            int minIndex = left;
            int maxIndex = right;


            //每次查找,保证arr[minIndex] <= arr[maxIndex]
            if (arr[minIndex] > arr[maxIndex]) {
                swap(arr, minIndex, maxIndex);
            }
            //从left+1到right-1遍历,找出最大最小
            for (int i = left + 1; i < right; i++) {
                if (arr[i] < arr[minIndex])
                    minIndex = i;
                else if (arr[i] > arr[maxIndex])
                    maxIndex = i;
            }

            swap(arr, left, minIndex);
            swap(arr, right, maxIndex);

            left++;
            right--;
        }

    }

插入排序

依次交换

从i位置向前依次进行比较,如果比本身大,就交换一下,直到正确位置

     /** * 插入排序1 * 和前一个一次交换,直到正确位置 * * @param arr */
    public static void InsertionSort1(int[] arr) {

        int n = arr.length;
        for (int i = 0; i < n; i++) {
            //寻找arr[i]适合的地方插入
            for (int j = i; j > 0 && arr[j] < arr[j - 1]; j--) {
                swap(arr, j, j - 1);
            }
        }
    }
依次覆盖

先暂存本身的值
从 i 位置开始向前遍历,如果arr[j-1[>arr[j] 就让arr[j-1[覆盖arr[j[的值,直到找到正确位置,将本身的值填进去

	/** * 插入排序2 * 暂存插入的数据 * 将前一个元素循环赋值给后一个元素,当发现正确位置后,将暂存数据放到对应位置 * * @param arr */
    public static void InsertionSort2(int[] arr) {

        int n = arr.length;
        for (int i = 0; i < n; i++) {
            int e = arr[i];
            int j = i;
            for (; j > 0 && e < arr[j - 1]; j--) {
                arr[j] = arr[j - 1];
            }
            arr[j] = e;
        }
    }

冒泡排序

常规冒泡

从第一个数开始遍历,发现大于后面的数就交换,交换之后继续比较,直到有序

	/** * 冒泡排序1 * 从头到尾全部遍历了 * * @param arr */
    public static void BubbleSort1(int[] arr) {

        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                }
            }
        }
    }
优化冒泡

从第一个数开始遍历,发现大于后面的数就交换,交换之后继续比较
每次交换都记录下标记位,最后一次更新的标记位后都是有序的了,外层遍历到标记位就退出,减少了遍历次数,如果是基本有序的,最好情况可升级至O(N)

	 /** * 冒泡排序2 * 如果后面m个有序,记录位置,每次遍历到有序位就跳出来 * * @param arr */
    public static void BubbleSort2(int[] arr) {

        int n = arr.length;
        int new_n;
        do {

            new_n = 0;
            for (int i = 1; i < n; i++) {
                if (arr[i - 1] > arr[i]) {
                    swap(arr, i - 1, i);
                    new_n = i;
                }
            }
            //每次发现无序就交换一下,最后一次交换之后的都是有序的了,下次就不遍历有序这部分了
            n = new_n;

            //都有序了,不发生互换,new_n == 0 就退出
        } while (new_n > 0);
    }

希尔排序

	/** * 希尔排序 * @param arr */
    public static void ShellSort(int[] arr) {

        int n = arr.length;
        //增量
        int gap = 1;
        while (gap < n / 3) {
            gap = gap * 3 + 1;
        }
        while (gap >= 1) {
            for (int i = gap; i < n; i++) {
                //使用插入排序
                int e = arr[i];
                int j = i;
                for (; j >= gap && e < arr[j - gap]; j -= gap) {
                    arr[j] = arr[j - 1];
                }
                arr[j] = e;
            }
            gap /= 3;
        }
    }

归并排序

 /** * 归并排序递归方法体 * * @param arr * @param l * @param mid * @param r 将arr[l...mid]和arr[mid+1...r]两部分进行归并 */
    private static void merge(int[] arr, int l, int mid, int r) {

        //暂存原始数据
        int[] aux = Arrays.copyOfRange(arr, l, r + 1);

        //初始化
        int i = l, j = mid + 1;
        for (int k = l; k <= r; k++) {

            if( i > mid ){  // 如果左半部分元素已经全部处理完毕
                arr[k] = aux[j-l]; j ++;
            }
            else if( j > r ){   // 如果右半部分元素已经全部处理完毕
                arr[k] = aux[i-l]; i ++;
            }
            else if( aux[i-l]<aux[j-l]){  // 左半部分所指元素 < 右半部分所指元素
                arr[k] = aux[i-l]; i ++;
            }
            else{  // 左半部分所指元素 >= 右半部分所指元素
                arr[k] = aux[j-l]; j ++;
            }
        }
    }

    //递归调用归并排序,对arr[l...r]的范围进行排序
    private static void MergeSorts(int[] arr, int l, int r) {

        if (l >= r) {
            return;
        }

        int mid = (l + r) / 2;

        //下探到下一层进行归并
        MergeSorts(arr, l, mid);
        MergeSorts(arr, mid + 1, r);

        //本层操作,进行归并排序
        merge(arr, l, mid, r);

    }

    /** * 归并排序 * * @param arr */
    public static void MergeSort(int[] arr) {
        MergeSorts(arr, 0, arr.length - 1);
    }

快速排序

普通快速排序
  • 每次选第一个数称为 “基准”(pivot);
  • 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;
  • 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序
	//对arr[l...r]部分进行partition
    private static int partition(int[] arr, int l, int r) {

        //暂存arr[l]
        int v = arr[l];
        //j为分割位
        int j = l;
        for (int i = l + 1; i <= r; i++) {
            if (arr[i] < v) {
                j++;
                //将小于v的这个数和第一个大于v的数交换
                swap(arr, j, i);
            }
        }
        //将v交换到分割位
        swap(arr, l, j);

        return j;
    }


    //递归使用快速排序
    private static void quickSort1(int[] arr, int l, int r) {

        if (l >= r) {
            return;
        }


        //获取l位置这个数的正确位置
        int p = partition(arr, l, r);

        //小于v的部分递归
        quickSort1(arr, l, p - 1);
        //大于v的部分递归
        quickSort1(arr, p + 1, r);

    }
	//主调用
    static void quickSort1(int[] arr) {
        quickSort1(arr, 0, arr.length - 1);
    }


    private static void swap(int[] arr, int i, int j) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
随机快速排序

每次都从第一个数作为基准,最坏情况下会退化成n^2

改进:将基准的获取随机化,期望变为nlogn

swap( arr, l , (int)(Math.random()*(r-l+1))+l );

修改partition,添加上随机化代码

	//对arr[l...r]部分进行partition
    private static int partition(int[] arr, int l, int r) {

        // 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot
        swap( arr, l , (int)(Math.random()*(r-l+1))+l );


        //暂存arr[l]
        int v = arr[l];
        //j为分割位
        int j = l;
        for (int i = l + 1; i <= r; i++) {
            if (arr[i] < v) {
                j++;
                //将小于v的这个数和第一个大于v的数交换
                swap(arr, j, i);
            }
        }
        //将v交换到分割位
        swap(arr, l, j);

        return j;
    }
双路快速排序



图自慕课网bobo老师的算法与数据结构课程!

i索引不断向后扫描,当i的元素小于v的时候继续向后扫描,直到碰到了某个元素大于等于v。j同理,直到碰到某个元素小于等于v。

然后绿色的部分便归并到了一起,而此时只要交换i和j的位置就可以了,然后i++,j–就行了。

代码仅需要修改partition

 // 双路快速排序的partition
    // 返回p, 使得arr[l...p-1] <= arr[p] ; arr[p+1...r] >= arr[p]
    //对arr[l...r]部分进行partition
    private static int partition(int[] arr, int l, int r) {

        // 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot
        swap(arr, l, (int) (Math.random() * (r - l + 1)) + l);


        //暂存arr[l]
        int v = arr[l];

        //j为分割位
        int i = l + 1, j = r;
        while (true) {

            //从前面开始。小于v的不变
            while (i <= r && arr[i] < v) {
                i++;
            }
            //从后面开始。大于v不变
            while (j >= l + 1 && arr[j] > v) {
                j--;
            }

            if (i > j) {
                break;
            }

            //到这里了: arr[i]>=v arr[j]<=v
            //如果等于v也要换,保证了两边相等的数目平衡

            swap(arr, i, j);
            i++;
            j--;
        }
        swap(arr, l, j);
        return j;
    }
三路快速排序



当重复数字较多时,以上三种快速排序效率都很低,所以需要将==v单独进行处理,具体如图和代码,感觉看代码比说更清楚

 	// 三路快速排序的partition
    //对arr[l...r]部分进行partition
    private static void quickSort3(int[] arr, int l, int r) {

        if (l > r) {
            return;
        }

        // 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot
        swap(arr, l, (int) (Math.random() * (r - l + 1)) + l);


        //暂存arr[l]
        int v = arr[l];

        //j为分割位
        int lt = l;
        int gt = r + 1;
        int i = l + 1;
        while (i < gt) {

            if (arr[i] < v) {
                swap(arr, i, lt + 1);
                i++;
                lt++;
            } else if (arr[i] > v) {
                swap(arr, i, gt - 1);
                gt--;
            } else {
                i++;
            }
        }
        swap(arr, l, lt);

        //小于v的部分递归
        quickSort3(arr, l, lt - 1);
        //大于v的部分递归
        quickSort3(arr, gt, r);

    }


    static void quickSort3(int[] arr) {
        quickSort3(arr, 0, arr.length - 1);
    }


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

堆排序

优先队列

个人觉得这个很丑,面试要被怼,不过也算是一种方法嘛,利用了Java的优先队列底层是小顶堆的特性,只要存入优先队列再取出来就是按堆排序实现了

	static void heapSort(int[] arr) {

        PriorityQueue<Integer> pq = new PriorityQueue<>();

        for (int i = 0; i < arr.length; i++) {
            pq.add(arr[i]);
        }
        for (int i = 0; i < arr.length; i++) {
            arr[i] = pq.remove();
        }

    }
原地堆

上面的图就是原地堆的,看不懂我写的就看图吧!!!

首先直接把传入的数组就当做无序的完全二叉树

先判断最后一个非叶子节点的位置,从它开始向前进行siftDown操作

这样,我们就构建成了一个大顶堆,堆顶就是最大值啦

然后把最大值放到倒数对应的位置去,后面的数就有序了

后面的数移到堆顶打破了堆的结构,再次进行siftDown操作,这时候就要限制siftDown操作的堆的范围了,只在无序的部分进行siftDown操作

最终所有值都放到对应的位置

	static void heapSort2(int[] arr) {

        int n = arr.length;

        // 注意,此时我们的堆是从0开始索引的
        // 从(最后一个元素的索引-1)/2开始(最后一个叶子节点父节点)
        // 最后一个元素的索引 = n-1
        for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
            siftDown(arr, n, i);
        }

        for (int i = n - 1; i > 0; i--) {
            swap(arr, 0, i);
            siftDown(arr, i, 0);
        }

    }

    /** * * @param arr 堆数组 * @param n 有序的位置 * @param k 当前位置 */
    private static void siftDown(int[] arr, int n, int k) {
        while (2 * k + 1 < n) {
            //默认左孩子
            int j = 2 * k + 1;
            //看下有没有右孩子并且比左孩子大,如果有,就让它浮上去
            if (j + 1 < n && arr[j + 1] > arr[j])
                j += 1;

            if (arr[k] >= arr[j]) break;
            //孩子比父节点大,浮上去
            swap(arr, k, j);
            k = j;
        }
    }

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

计数排序

  • 找出待排序的数组中最大和最小的元素;
  • 统计数组中每个值为i的元素出现的次数,存入数组C的第i项;
  • 对所有的计数累加(从C中的第一个元素开始,每一项和前一项相加);
  • 反向填充目标数组:将每个元素i放在新数组的第C(i)项,每放一个元素就将C(i)减去1。
	/** * 计数排序 * * @param arr */
    static void countSort(int[] arr) {

        //获取数列的最大值和最小值,并求出差值
        int max = arr[0];
        int min = arr[0];
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > max)
                max = arr[i];
            if (arr[i] < min)
                min = arr[i];
        }
        int d = max - min;

        //常见统计数组并统计对饮元素的个数
        int[] countArr = new int[d + 1];
        for (int i = 0; i < arr.length; i++) {
            countArr[arr[i] - min]++;
        }

        //统计数组做变形,后面额元素等于前面的元素之和

        int sum = 0;
        for (int i = 0; i < countArr.length; i++) {
            sum += countArr[i];
            countArr[i] = sum;
        }

        //倒序遍历原始数列,从统计数字找出正确位置
        int[] res = new int[arr.length];
        for (int i = arr.length - 1; i >= 0; i--) {
            res[countArr[arr[i] - min] - 1] = arr[i];
            countArr[arr[i] - min]--;
        }


        //复制数据到原数组
        System.arraycopy(res,0,arr,0,res.length);
        
    }

桶排序

  • 设置一个定量的数组当作空桶,代码是假定传入为[0,10)之间的浮点数,以[0,9]的整数为桶
  • 遍历输入数据,并且把数据一个一个放到对应的桶里去;
  • 对每个不是空的桶进行排序;
  • 从不是空的桶里把排好序的数据拼接起来
 	 /** * 桶排序 * 假定传入为[0,10)之间的浮点数,以[0,9]的整数为桶 * * @param arr */
    private static void bucketSort(double[] arr) {
        //创建桶的集合
        ArrayList<LinkedList<Double>> buckets = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            buckets.add(new LinkedList<Double>());
        }

        //将数据放入桶并排序
        for (double data : arr) {
            //获取数据对应的桶序号
            int index = getIndex(data);
            //将数据放入桶并在桶内排序
            insertAndSort(buckets.get(index), data);
        }

        //将数据取出来
        int index = 0;
        for (LinkedList<Double> bucket : buckets) {
            for (double data : bucket) {
                arr[index++] = data;
            }
        }


    }

    //放入桶并排序
    private static void insertAndSort(LinkedList<Double> buckets, double data) {
        buckets.add(data);
        //排序,double比较需要重写一下比较规则
        buckets.sort(new Comparator<Double>() {
            @Override
            public int compare(Double o1, Double o2) {
                return o1.compareTo(o2);
            }
        });


    }

    //自定义规则的桶划分
    private static int getIndex(double data) {
        return (int) data;
    }

基数排序

  • 取得数组中的最大数,并取得位数;
  • arr为原始数组,从最低位开始取每个位组成radix数组;
  • 对radix进行计数排序(利用计数排序适用于小范围数的特点)
	/** * 基数排序 * * @param arr */
    private static void radixSort(int[] arr) {

        int n = arr.length;

        //find max
        int max = arr[0];
        for (int i = 1; i < n; i++) {
            if (arr[i] > max)
                max = arr[i];
        }
        //求最大值的位数
        int keyNum = 0;
        while (max > 0) {
            max /= 10;
            keyNum++;
        }

        //构建并初始化桶集合
        ArrayList<LinkedList<Integer>> buckets = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            buckets.add(new LinkedList<>());
        }

        for (int i = 0; i < keyNum; i++) {
            radixSort(arr, buckets, i);
        }


    }

    /** * 装入bucket后再写入arr * @param arr * @param buckets * @param num */
    private static void radixSort(int[] arr, ArrayList<LinkedList<Integer>> buckets, int num) {

        //将数据存入bucket
        for (int i = 0; i < arr.length; i++) {
            //获取key
            int key = (int) (arr[i] % Math.pow(10, num + 1) / Math.pow(10, num));
            
            buckets.get(key).add(arr[i]);
        }

        //读取数据到arr
        int count = 0;
        for (int i = 0; i < 10; i++) {
            LinkedList<Integer> bucket = buckets.get(i);
            while (!bucket.isEmpty()){
                arr[count++] = bucket.remove();
            }

        }


    }

更多Java面试复习笔记和总结可访问我的面试复习专栏《Java面试复习笔记》,或者访问我另一篇博客《Java面试核心知识点汇总》查看目录和直达链接