首页 > 代码库 > 快速排序算法
快速排序算法
快速排序
快速排序属于交换排序中的一种,它通过选定一个元素为中间元素,然后将表中所有元素与该中间元素相比较,将表中比中间元素小的放到表前面,大的放表后面,再将中间元素放置在这两部分之间作为分界点,这样便得到一个划分,使左边的元素都小于右边的,然后对左边与右边的再进行快速排序。
Java代码实现如下
public class QuickSort { public static void main(String[] args) { int[] arr = { 6, 3, 7, 10, 2, 9, 15, 10, 8, 17 }; qsort(arr, 0, arr.length - 1); for (int temp : arr) { System.out.println(temp); } } private static void qsort(int[] arr, int low, int high) { if (low < high) { int pivot = partition(arr, low, high); // 将数组分为两部分 qsort(arr, low, pivot - 1); // 递归排序左子数组 qsort(arr, pivot + 1, high); // 递归排序右子数组 } } private static int partition(int[] arr, int low, int high) { int pivot = arr[low]; // 保存中间元素以腾出空位 while (low < high) { while (low < high && arr[high] >= pivot) --high; arr[low] = arr[high]; // 交换比中间元素小的记录到左端 while (low < high && arr[low] <= pivot) ++low; arr[high] = arr[low]; // 交换比中间元素小的记录到右端 } // 扫描完成 arr[low] = pivot; // 返回的是中间元素的位置 return low; }}
快速排序算法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。