Java递归和非递归实现快排前言一、快速排序基本逻辑二、过程演示三、实现代码总结
前言
最近复习数据结构，顺便复习快速排序的过程。
一、快速排序基本逻辑
快排以某个关键字为基准，将待排序序列分成两部分，其中一部分数据都比它小，另外一部分数据都比它大，每分两部分一次算作一次划分。每步都将表中第一个元素（通常情况下选择待排序序列第一个元素记作基准）确定到它在表中的最终位置，同时在这个元素开始前后各划分出一个子表，之后对每个子表也进行不断划分，直到每个子表只有一个元素排序完成。
二、过程演示
递归方式：
package sort;import java.util.Scanner;public class Quick_Sort1 { public static int part(int[] arr, int low, int high) { //arr[0]存放基准 arr[0] = arr[low]; while (low < high) { while (arr[high] >= arr[0] && low < high) { high--; } arr[low] = arr[high]; while (arr[low] <= arr[0] && low < high) { low++; } arr[high] = arr[low]; } arr[low] = arr[0]; return low; } public static void QSort(int[] arr, int low, int high) { //判断是不是仅有一个元素 if (low < high) { int mid = part(arr, low, high); //排序左半部分 QSort(arr, low, mid - 1); //排序右半部分 QSort(arr, mid + 1, high); } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.print("输入数据个数:"); int n = sc.nextInt(); //多申请一个空间，arr[0]存放基准，数据从1开始存 int arr[] = new int[n + 1]; System.out.print("输入数据:"); for (int i = 1; i <= n; i++) { arr[i] = sc.nextInt(); }//调用快排 QSort(arr, 1, n); for (int i = 1; i <= n; i++) { System.out.print(arr[i] + " "); } }}
非递归方式(调用栈)
package sort;import java.util.Scanner;import java.util.Stack;public class Quick_Sort2 { public static int part(int[] arr, int low, int high) { arr[0] = arr[low]; while (low < high) { while (low < high && arr[high] >= arr[0]) { high--; } arr[low] = arr[high]; while (low < high && arr[low] <= arr[0]) { low++; } arr[high] = arr[low]; } arr[low] = arr[0]; return low; } public static void QSort(int[] arr, int low, int high) { Stack
快排是一个不稳定的排序方法，理想条件下时间复杂度为O(n log n)，在数列有序情况下退化成冒泡排序，时间复杂度为O(n*n)。