排序算法之快速排序原理与实战

公告：“业余草”微信公众号提供免费CSDN下载服务(只下Java资源)，关注业余草微信公众号，添加作者微信：xttblog2，发送下载链接帮助你免费下载！
本博客日IP超过2000，PV 3000 左右，急需赞助商。
极客时间所有课程通过我的二维码购买后返现24元微信红包，请加博主新的微信号：xttblog2，之前的微信号好友位已满，备注：返现
受密码保护的文章请关注“业余草”公众号，回复关键字“0”获得密码
所有面试题(java、前端、数据库、springboot等)一网打尽，请关注文末小程序

腾讯云】1核2G5M轻量应用服务器50元首年，高性价比，助您轻松上云

说道排序，我相信大家并不模式。在写程序的生涯中我们随处可见到排序的使用场景，例如数据库sql排序。排序的算法有很多种，同时java等语言也都提供了排序的接口，方便大家进行简单排序功能。关于排序算法有很多种，如快速排序、直接插入排序、希尔排序、简单选择排序、二元选择排序、冒泡排序等。这些排序我将写一系列的文章进行原理解析和实例演示。

快速排序的原理是：使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
基本思想：选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描，将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。
快速排序分解图如下：

快速排序具体实例源码如下：

package com.xttblog.sort;

public class QuickSort {
	//快速排序
	private static void quickSort(int s[], int l, int r){
		if(l>=r)
			return;
	    //将中间的这个数和第一个数交换 参见注1
		int i = l, j = r, x = s[l];
		while (i < j){
			while(i < j && s[j] >= x) // 从右向左找第一个小于x的数
				j--;  
			if(i < j) 
				s[i++] = s[j];
			
			while(i < j && s[i] < x) // 从左向右找第一个大于等于x的数
				i++;  
			if(i < j) 
				s[j--] = s[i];
		}
		s[i] = x;
		quickSort(s, l, i - 1); // 递归调用 
		quickSort(s, i + 1, r);
	}
	
	public static void main(String[] args) {
		int s [] = {67,23,89,35,28,90,10,24};
		for (int i : s) {
			System.out.print(i+" ");
		}
		quickSort(s,0,7);
		System.out.println();
		for (int i : s) {
			System.out.print(i+" ");
		}
		//排序前后输入结果为：
		//67 23 89 35 28 90 10 24 
		//10 23 24 28 35 67 89 90 
	}
}

版权声明：本文为博主原创文章，未经博主允许不得转载。原文地址http://www.xttblog.com/?p=433

最后，欢迎关注我的个人微信公众号：业余草（yyucao）！可加作者微信号：xttblog2。备注：“1”，添加博主微信拉你进微信群。备注错误不会同意好友申请。再次感谢您的关注！后续有精彩内容会第一时间发给您！原创文章投稿请发送至532009913@qq.com邮箱。商务合作也可添加作者微信进行联系！

本文原文出处：业余草： » 排序算法之快速排序原理与实战