RuiCode

  • 首页
  • 归档

  • 搜索
操作系统 并发 排序 网络 源码分析 二分法 面试 不重复算法 指针移动 java 算法 mysql Linux

快速排序总结

发表于 2020-02-23 | 分类于 面试经 | 0 | 阅读次数 414

核心:

  • 每次以left index作为基准数字
  • 先从右向左找第一个比基准数字小的数,再从左向右找比基准数字大的数。这样最后leftPoint == rightPoint 时,nums[rightPoint] 总是比基准数字小或者就是基准数字,可以放心的交换,保证交换后的nums[left] 不大于基准数字
  • 和基准数字相同的数不用管,经过递归后,总能交换到基准数字附近
  • 每递归一次,就能保证基准数字在准确的index上,并且左边的数不大于基准数字,右边的数不小于基准数字
  • 归并排序的目的是先让小范围数组有序,再让大范围数组有序
package com.company;

import java.util.Arrays;

public class QuickSort {

    public static void main(String[] args) {
	    int[] nums= new int[]{6,4,2,6,7,4,8,9,3,1};
	    quickSort(nums, 0, nums.length);
        System.out.println(Arrays.toString(nums));
    }

    public static void quickSort(int[] nums, int left, int right) {
        if(left >= right) {
            return;
        }
        int standard = nums[left];
        int leftPoint = left;
        int rightPoint = right-1;
        while(leftPoint<rightPoint) {
            while (nums[rightPoint] >= standard && leftPoint<rightPoint){
                rightPoint--;
            }
            while (nums[leftPoint] <= standard && leftPoint<rightPoint) {
                leftPoint++;
            }
            if(leftPoint < rightPoint) {
                int temp = nums[leftPoint];
                nums[leftPoint] = nums[rightPoint];
                nums[rightPoint] = temp;
            }
        }
        nums[left] = nums[leftPoint];
        nums[leftPoint] = standard;
        quickSort(nums, left, leftPoint);
        quickSort(nums, leftPoint+1, right);
    }


}
  • 本文作者: RuiCode
  • 本文链接: https://www.ruicode.cn/archives/快速排序总结
  • 版权声明: 本博客所有文章除特别声明外,均采用CC BY-NC-SA 3.0 许可协议。转载请注明出处!
# 操作系统 # 并发 # 排序 # 网络 # 源码分析 # 二分法 # 面试 # 不重复算法 # 指针移动 # java # 算法 # mysql # Linux
【面试经】计算机网络1 -- TCP的建立和断开
【面试经】JAVA并发编程1--synchronized
  • 文章目录
  • 站点概览
RuiCode

RuiCode

19 日志
5 分类
13 标签
Creative Commons
© 2021 RuiCode
由 Halo 强力驱动
|
主题 - NexT.Pisces v5.1.4

冀公网安备 13050002001906号