快速排序其实是在冒泡排序的基础上做出的一个改进.
快速排序算法利用的是一趟快速排序,基本内容是选择一个数作为准基数,然后利用这个准基数将遗传数据分为两个部分,第一部分比这个准基数小,都放在准基数的左边,第二部分都比这个准基数大,放在准基数的右边.
接下来这两部分都是用快排(可以使用递归的方法)完成从小到大的排序.
首先需要了解一下冒泡排序,简单的说就是两两比较,交换位置.基本排序方法,都会,也不多说,就直接上代码.
public static void main(String[]args){
int[] arr ={23,25,12,7,51};
mao(arr);
shu(arr);
}
public static void mao(int[]arr){
for(int i=0;i<arr.length-1;i++){
for(int j=0;j<arr.length-i-1;j++){
if(arr[j+1]>arr[j]){
/*
* 从数组左边开始,两两比较;
* 如果后一个大于前一个,则将他们的值对换
* 定义一个中间变量
* 首先将前一个值赋给他,然后在将后一个数值赋给前一个数值,最后再将temp保存的较小的值赋给后一个数值
* 这样内层循环一次,就可以比较出一个较小的变量
* */
int temp =arr[j];
arr[j] = arr[j+1]; //将arr[j+1]的值赋给arr[j],程序是从右往左执行的
arr[j+1] =temp; //再将temp的值赋给arr[j+1]
}
}
}
}
public static void shu(int[]arr){
for(int i=0;i<arr.length;i++){
System.out.println(arr[i]);
}
}
有了这个基础过后,继续来看看快排.
首先第一步我们先建立一组数据:
12 30 5 16 20 数据
0 1 2 3 4 下标
1.根据快排规则,我们先定下一个准基数,通常准基数都是数据的第一位,也就是这里的12
2.然后一趟快排是先从下标4向左进行和准基数（12）的比较，比较完一个后，然后再从下标0向右进行和准基数（12）的比较
3.我们进行比较的规则和操作是：从下标6向左进行和准基数（12）的比较，只要遇到的数据小于准基数（12）的时候我们就将这个数和准基数（12）进行替换，然后再执行从下标0向右进行和准基数（12）的比较
(12)—5 30 (5)---->12 16 20 数据
0 1 2 3 4 下标
4.我们再从下标0向右进行和准基数（12）的比较,30>12,交换位置
5 (30)—>12 (12)—30 16 20 数据
0 1 2 3 4 下标
5.这就完成一趟快排了,一趟快排指一个准基数从末尾下标向前比较遇到一个比准基数小的数后,再从开始下标向后比较遇到一个比准基数大的,再利用递归的思想,重复使用,完成排序
代码实现:
package test7;
public class Demo14{
public static void main(String[] args) {
int[] a = {12,20,5,16,15,1,30,45,23,9,4,4};
int min = 0;
int max = a.length-1;
sort(a, min, max);
for (int i : a) {
System.out.println(i);
}
}
/*
* 首先需要一个数组存放所有的数据
* 定一个开始位置和一个结束为止
* 选择一个数作为准基数
*/
public static void sort(int a[],int min,int max) {
int key=a[min];//准基数
int start=min; //开始位置
int end =max;//结束位置
while(end>start) { //循环条件是否数值交叉
//从后开始往前查找
while(end>start&&a[end]>=key) {
//如果找到的值大于基数值，那么继续往下找，end--
end--;
}
//如果找到的值小于基数值，那么进行值交换
if(a[end]<key) {
int i=a[end];
a[end]=a[start];
a[start]=i;
}
//从前往后找
while(end>start&&a[start]<=key) {
//如果找到的值小于基数值，那么继续往下找，start++
start++;
}
//如果找到的值大于基数值，那么进行值交换
if(a[start]>key) {
int i=a[start];
a[start]=a[end];
a[end]=i;
}
}
//这部分的数据都是小于准基数，通过递归在进行一趟快排
if(start>min) {
sort(a, min, start-1); //开始位置为第一位，结束位置为关键索引-1
}
if(end<max) {
sort(a, end+1, max); //开始位置为关键索引+1，结束位置最后一位
}
}
}
