一、排序思想
快速排序是由冒泡排序改进而得到的,是一种分区交换排序方法。思想如下:
一趟快速排序采用从两头向中间扫描的方法,同时交换与基准记录逆序的记录。
- 在待排序的N个记录中任取一个元素(通常取第一个记录)作为基准,称为基准记录;
- 定义两个索引 left 和 right 分别表示“首索引” 和 “尾索引”,key 表示“基准值”;
- 首先,尾索引向前扫描,直到找到比基准值小的记录(left != righ),并替换首索引对应的值;
- 然后,首索引向后扫描,直到找到比基准值大于的记录(left != righ),并替换尾索引对应的值;
- 若在扫描过程中首索引等于尾索引(left = right),则一趟排序结束;将基准值(key)替换首索引所对应的值;
- 再进行下一趟排序时,待排序列被分成两个区:[0,left-1],[righ+1,end]
- 对每一个分区重复步骤2~6,直到所有分区中的记录都有序,排序成功。
二、图解
三、代码实现
/** * 快速排序演示 * @author Lvan */ public class QuickSort { public static void main(String[] args) { int[] arr = {5, 1, 7, 3, 1, 6, 9, 4}; quickSort(arr, 0, arr.length - 1); for (int i : arr) { System.out.print(i + "\t"); } } /** * @param arr 待排序列 * @param leftIndex 待排序列起始位置 * @param rightIndex 待排序列结束位置 */ private static void quickSort(int[] arr, int leftIndex, int rightIndex) { if (leftIndex >= rightIndex) { return; } int left = leftIndex; int right = rightIndex; //待排序的第一个元素作为基准值 int key = arr[left]; //从左右两边交替扫描,直到left = right while (left < right) { while (right > left && arr[right] >= key) { //从右往左扫描,找到第一个比基准值小的元素 right--; } //找到这种元素将arr[right]放入arr[left]中 arr[left] = arr[right]; while (left < right && arr[left] <= key) { //从左往右扫描,找到第一个比基准值大的元素 left++; } //找到这种元素将arr[left]放入arr[right]中 arr[right] = arr[left]; } //基准值归位 arr[left] = key; //对基准值左边的元素进行递归排序 quickSort(arr, leftIndex, left - 1); //对基准值右边的元素进行递归排序。 quickSort(arr, right + 1, rightIndex); } }
今天的文章简单快速排序_实现快速排序分享到此就结束了,感谢您的阅读,如果确实帮到您,您可以动动手指转发给其他人。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/53371.html