(3)交换排序之快速排序
- 2019 年 10 月 4 日
- 筆記
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_37933685/article/details/88681552
title: (3)交换排序之快速排序 date: 2019-03-12 13:00:00 +0800 update: 2019-03-12 13:00:00 +0800 author: me cover: http://ww1.sinaimg.cn/large/006jIRTegy1g17bc4qzxuj31kw11xne5.jpg preview: 快速排序是一个知名度极高的排序算法,对大数据的优秀排序性能和相同复杂度算法中相对简单的实现 tags:
- 算法
文章目录
(3)交换排序之快速排序
算法演示图
代码实现
public static void quickSort(int[] arr){ qsort(arr, 0, arr.length-1); } 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; }