[Java]快速排序算法完整代码

快排作为排序算法里的明星算法，大家当然是要掌握的啦！
作为小白的时候觉得它很高大上很难，其实一点也不难的，大家动手敲几遍就能掌握。
另外虽然这里是用Java实现的，但其实一点也没用到java的特性，用C、C++来写也都是一样的

• 核心只有quickSort 这一个函数

package leetcode;import java.util.Arrays;
import java.util.Scanner;/*** 演示快速排序算法，平均时间复杂度O(nlogn) 最差情况O(n2)*/
public class QuickSort {public static void main(String[] args) {//先接收输入System.out.print("请输入数列长度n： ");Scanner sc = new Scanner(System.in);int n = sc.nextInt(); //长度nint[] a = new int[n]; //用a数组中保存n个数System.out.println("请输入n个数,空格分隔：");for (int i = 0; i < n; i++) {a[i] = sc.nextInt();}//调用快排函数quickSort(a,0,n-1);System.out.println("快速排序结果是：");System.out.println(Arrays.toString(a)); //输出排序后的数组}//对a[left,right]区间内的数进行快排public static void quickSort(int[] a, int left , int right) {if(left >= right) { //区间内只有一个元素或没有元素时就不必排了,这也是递归出口return ;}int i = left , j = right; // i、j就为我们要移动的两个指针，初始化i为左边界，j为右边界int index = left;   //index是基准元的下标，我们取首元素作为基准元while (i < j) {while(a[j] > a[index] && i != j) { //右指针j要找到第一个小于基准元的元素下标，所以只要大于就向左移j--;}while (a[i] <= a[index] && i != j) { //左指针i要找到第一个大于基准元的元素下标，所以只要小于等于就右移i++;}if(i != j) { //如果i、j还没相遇，说明它们找到了一对“逆序对”，于是交换,交换以后不移动指针，进行下一轮的循环int temp = a[i];a[i] = a[j];a[j] = temp;}//如果i、j相遇说明这轮遍历已经结束了，不再符合i < j的条件，跳出循环}if(i == j) { //一次遍历完成，交换基准元，递归int temp = a[index];a[index] = a[i];a[i] = temp;//现在a[i]已经归位了，下面递归排序[left,i-1]、[i+1,right]这两个子区间quickSort(a,left,i-1); //当前i = j，用i或者j都行quickSort(a,i+1, right);}}
}

 运行截图： 

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！