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

JAVA herman 1624浏览 0评论
公告:“业余草”微信公众号提供免费CSDN下载服务(只下Java资源),关注业余草微信公众号,添加作者微信:xttblog,发送下载链接帮助你免费下载!
本博客日IP超过1800,PV 2600 左右,急需赞助商。
极客时间所有课程通过我的二维码购买后返现24元微信红包,请加博主新的微信号:xttblog,之前的微信号好友位已满,备注:返现
所有面试题(java、前端、数据库、springboot等)一网打尽,请关注文末小程序
视频教程免费领

说道排序,我相信大家并不模式。在写程序的生涯中我们随处可见到排序的使用场景,例如数据库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)!可加QQ1群:135430763(2000人群已满),QQ2群:454796847(已满),QQ3群:187424846(已满)。QQ群进群密码:xttblog,想加微信群的朋友,之前的微信号好友已满,请加博主新的微信号:xttblog,备注:“xttblog”,添加博主微信拉你进群。备注错误不会同意好友申请。再次感谢您的关注!后续有精彩内容会第一时间发给您!原创文章投稿请发送至532009913@qq.com邮箱。商务合作可添加助理微信进行沟通!

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