博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
java实现快速排序算法
阅读量:5866 次
发布时间:2019-06-19

本文共 739 字,大约阅读时间需要 2 分钟。

1、算法概念。

快速排序(Quicksort)是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。

2、算法思想。

通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

3、实现思路。

①以第一个关键字 K 1 为控制字,将 [K 1 ,K 2 ,…,K n ] 分成两个子区,使左区所有关键字小于等于 K 1 ,右区所有关键字大于等于 K 1 ,最后控制字居两个子区中间的适当位置。在子区内数据尚处于无序状态。 

②把左区作为一个整体,用①的步骤进行处理,右区进行相同的处理。(即递归)
③重复第①、②步,直到左区处理完毕。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public
static
void
quickSortByMid(
int
[] a,
int
low,
int
high) {
    
if
(low >= high)
      
return
;
    
// 分割
    
int
pivot = a[low];
// 基准值
    
int
i = low, j = high;
    
while
(i < j) {
      
while
(i < j && a[j] >= pivot)
        
--j;
      
a[i]=a[j];
      
while
(i < j && a[i] <= pivot)
        
++i;
      
a[j]=a[i];
    
}
    
a[i]=pivot;
    
quickSortByMid(a, low, i-
1
);
    
quickSortByMid(a, i+
1
, high);
  
}

快速排序算法示意图:

转载地址:http://xpnnx.baihongyu.com/

你可能感兴趣的文章
rabbitmq学习记录(三)工作队列-轮询分配
查看>>
2. 红黑树
查看>>
开发者可在WindowsCoreOS创建自己的应用了
查看>>
eclipse常用快捷键
查看>>
iOS——拍照后的照片保存到本地
查看>>
es6对象笔记
查看>>
Java 堆内存与栈内存异同(Java Heap Memory vs Stack Memory Difference)
查看>>
初入博客
查看>>
如何从平面设计转行到UI设计?
查看>>
Java List序列化的实现
查看>>
Dart 服务端开发 文件上传
查看>>
python 模板语言之母本继承
查看>>
iOS多Target开发
查看>>
合理设置工作线程数
查看>>
1.Spring简介
查看>>
在虚拟机部署tp5的框架报错404及验证码出不来的解决思路
查看>>
C++复习(第二节)指针
查看>>
Object类有哪些方法
查看>>
6月8日任务 Nginx访问日志、Nginx日志切割、静态文件不记录日志和过期时间
查看>>
MySQL主从知识扩展
查看>>