排序算法-快速排序
2021/12/23 1:19:37
本文主要是介绍排序算法-快速排序,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
1、快速排序
快速排序(Quicksort)是对冒泡排序算法的一种改进。
算法思路
快速排序算法的排序流程如下:
- 1.先从数列中取出一个数作为基准数。
- 2.分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。
- 3.再对左右区间重复第二步,直到各区间只有一个数。
一趟快速排序的算法是:
1)设置两个变量i、j,排序开始的时候:i=0,j=N-1;
2)以第一个数组元素作为基准数,赋值给pivot,即pivot=A[0]=A[i];
3)由后向前搜索(j--),找到第一个小于pivot的值A[j],将A[j]和A[i]的值交换;
4)由前向后搜索(i++),找到第一个大于pivot的A[i],将A[i]和A[j]的值交换;
5)重复第3、4步,直到i==j;
经过第1趟排序,数组被划分为两个区,5左边是小于5的{2,3,0,1,4},Flag右边是大于Flag的{6,7,9,10,8}。我们再分别对这两个区进行递归操作,直至每个组里只剩下1个数字,排序完成!
代码
package com.hsp.baselearn.algorithm; import java.util.Arrays; /** * 快速排序 */ public class QuickSort { public static void main(String[] args) { int[] arr = { 5, 3, 7, 6, 4, 1, 0, 2, 9, 10, 8 }; quickSort(arr,0,arr.length-1); System.out.println(Arrays.toString(arr)); } private static void quickSort(int[] arr,int low,int hige) { if(low<hige){ // 1. 定义基准pivot, int pivot = arr[low]; // ...... pivot移动到中间,左边都比pivot小,后边都比pivot大, index int i= low; int j= hige; while (i<j){ //移动右边 while (i<j && arr[j]>=pivot){ j--; } //交换位置 swap(arr,i,j); //移动左边元素 while (i<j && arr[i]<=pivot){ i++; } //交换位置 swap(arr,i,j); } //此时j=1 递归对左右2部分快排 quickSort(arr,low,j-1); quickSort(arr,j+1,hige); } } private static void swap(int[] arr,int i,int j){ int temp = arr [i]; arr[i]=arr[j]; arr[j]=temp; } }
这篇关于排序算法-快速排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-20测试人员都是画画大神,让我看看谁还不会用代码图?
- 2024-05-20年薪百万的程序员都在用的摸鱼方式……
- 2024-05-19永别了,微服务架构!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了