程序员石同尘的Java笔记

快速排序示范-从小到大 关键操作“记录下标,使用递归”

2018-11-07  本文已影响11人  448f984add9e

        快速排序分析:关于数组下标的操作问题,一定要注意条件循环变量的初始值设置以及循环结束条件的判定,注意条件结构的多变量控制,有时候这很绕,比较吃熟练度,所以要多训练。才能使循环有效,避免数组越界等问题出现。

                          快速排序的一趟操作效果(方法体)是:1.把传入数组分成三部分,第一部分是一个子数组(传入数组的一部分呵),第二部分是一个数,第三部分还是一个子数组,这个数叫做中间数,既然这么个叫法,那么你肯定能理解中间数的左边数组也就是第一部分的所有数组元素都是小于或者等于这个中间数的,第二部分的所有数组元素都大于等于这个中间数的。2.接着分别让第一部分和第三部分子数组作为新的传入数组分别调用方法本身,即使用递归。这个递归结束的标志呢,就是当传入的数组是个单元素数组(数组只包含一个元素,当然就不需要排序了啊)的时候就停止了,这样一来原来的数组元素已经全部排序完毕。

我个人代码实现,注释说明:

public class QuickSort {

public static void quickSort(int[] array,int startIndex,int endIndex) {//准备传入 数组,首元素下标,尾元素下标

if(startIndex<endIndex) {//单元素数组就停止操作,因为不需要排序

int LR=startIndex+1,RL=endIndex;//记录数组元素下标的两个变量

while(true) {

for(int i=startIndex+1;i<=endIndex;i++) {//记录从左到右第一个大于等于首元素的下标

if(array[i]>=array[startIndex]) {

LR=i;

break;

}

LR++;

}

for(int j=endIndex;j>=startIndex+1;j--) {//记录从右到左第一个小于等于首元素的下标

if(array[j]<=array[startIndex]) {

RL=j;

break;

}

RL--;

}

if(LR<RL) {//若记录大于等于首元素的下标值 小于 记录小于等于首元素的下标值  那么这两个下标代表的元素值交换,接着循环

int temp=array[LR];

array[LR]=array[RL];

array[RL]=temp;

}else {

break;

}

}

if(LR>=RL) {//若记录大于等于首元素的下标值 大于 记录小于等于首元素的下标值 那么将记录小于等于首元素的下标代表的元素值与首元素值交换

int temp=array[RL];//,此时首元素值变成中间数,中间数左边是一子数组,右边是另一子数组

array[RL]=array[startIndex];

array[startIndex]=temp;

quickSort(array,startIndex,RL-1);//中间数左子数组(用三个传入参数表示)作为参数调用方法本身,即使用递归

quickSort(array,RL+1,endIndex);//中间数右子数组(用三个传入参数表示)作为参数调用方法本身,即使用递归

}

}

}

public static void main(String[] args) {

int[] array= {26,17,5,33,87,53,27,49,28,78};// TODO Auto-generated method stub

System.out.println("排序前:");

for(int i=0;i<array.length;i++)

System.out.print(array[i]+" ");

System.out.println();

quickSort(array,0,array.length-1);

System.out.println("排序后:");

for(int i=0;i<array.length;i++)

System.out.print(array[i]+" ");

}

}

运行结果:

排序前:

26 17 5 33 87 53 27 49 28 78

排序后:

5 17 26 27 28 33 49 53 78 87

上一篇 下一篇

猜你喜欢

热点阅读