原创

常用排序:冒泡排序与快速排序详解,看完这篇就够了!

常用排序:冒泡排序与快速排序详解。

在排序算法中,冒泡排序和快速排序可以算是排序算法入门必会的两种排序了,今天和大家来分析一下如何快速理解并掌握这两种排序。首先冒泡排序是初学者最常用的排序,所以我们先来详解下冒泡排序。

1.冒泡排序

冒泡排序,看字面意义就是有大泡泡和小泡泡在水中同时上浮,而大的泡泡就上升的快,小的泡泡就上升的相对较慢,从而产生了一定的速度差,这就产生了大的泡泡在小的泡泡上面,也就是按从一定的大小顺序排好了顺序。当然,这里的比喻和冒泡排序有点不同,冒泡排序是针对数值排序,且算法是有稍微的差别。

这里我们使用大家喜欢的java语言来示范,我们取出20个10以内的数字:

int[] sortInts = new int[20];
for (int i = 0; i < 20; i++) {
int random = (int) (Math.random() * 10);
sortInts[i] = random;
}

例如我们得到以下数值:

2、8、6、6、6、9、5、1、9、2、7、3、9、8、9、0、9、2、0、6、

下面要对这些数字进行冒泡排序,我们使用的方法是,两两对比,拿数组第一个数值对比第二个数值并把较大的替换到后面,然后是第一个数值对比第三个数值把较大的替换到后面,然后是第一个数值对比第四个数值把较大的替换到后面,直到对比到最后一个,第一轮对比结束。

第一轮对比结果:

0、8、6、6、6、9、5、2、9、2、7、3、9、8、9、1、9、2、0、6、

不难看出,第一个数值我们已经排序完成了,后面进行第二轮排序,我们拿第二个数值开始对比,第二个数值对比第三个数值并把较大的替换到后面,第二个数值对比第四个数值并把较大的替换到后面,直到对比到最后一个,第二轮对比结束。

第二轮对比结果:

0、0、8、6、6、9、6、5、9、2、7、3、9、8、9、2、9、2、1、6、

后面延续这样的对比最终排序完成。上面是理解层面的解释,下面给出代码实现:

    public static void main(String args[]){
int[] sortInts = new int[20];
for (int i = 0; i < 20; i++) {
int random = (int) (Math.random() * 10);
sortInts[i] = random;
}
printArrays(sortInts);
bubbleSort(sortInts);
}

//冒泡排序
private static void bubbleSort(int[] integers){
for(int i = 0; i<integers.length-1; i++){
for(int j=i; j<integers.length; j++){
if(integers[i] > integers[j]){
int temp = integers[i];
integers[i] = integers[j];
integers[j] = temp;
}
}
}
printArrays(integers);
}

private static void printArrays(int[] a) {
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + "、");
}
}

冒泡排序结果:

0、0、1、2、2、2、3、5、6、6、6、6、7、8、8、9、9、9、9、9、


注:本文来自风马博客原创,如有不对之处请留言指出。

2.快速排序

快速排序是冒泡排序的一种优化,稍微比冒泡排序要难理解一点点,快速排序的优点就是快速,缺点是不稳定。

快速排序的原理:

1.取数组中一个数值作为基数.

2.把大于此基数的换到数组的右侧,小于此基数的换到数组的左侧.

3.对换基数与中间数值的位置

4.重复2操作,直到数值数量为1

不难看出4步骤用到了递归方法,快速排序java实现代码如下:

 public static void main(String args[]){
int[] sortInts = new int[20];
for (int i = 0; i < 20; i++) {
int random = (int) (Math.random() * 10);
sortInts[i] = random;
}
printArrays(sortInts);
fastSort(sortInts,0,sortInts.length-1);
}

//快速排序
private static void fastSort(int[] integers,int left,int right){

if(left>right){
return;
}

int base = integers[left];
int i = left;
int j = right;
while(i < j){

while (integers[j]>=base && i<j){
j--;
}

while (integers[i]<=base && i<j){
i++;
}

int temp = integers[i];
integers[i] = integers[j];
integers[j] = temp;
}

integers[left] = integers[i];
integers[i] = base;

fastSort(integers,left,i-1);
fastSort(integers,i+1,right);

printArrays(integers);
}

private static void printArrays(int[] a) {
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + "、");
}
}

快速排序输出结果如下:

2、5、0、0、4、6、4、2、5、8、2、5、2、0、8、2、1、8、1、7、
0、0、0、1、1、2、4、2、5、8、2、5、2、6、8、2、4、8、5、7、
0、0、0、1、1、2、4、2、5、8、2、5、2、6、8、2、4、8、5、7、
0、0、0、1、1、2、4、2、5、8、2、5、2、6、8、2、4、8、5、7、
0、0、0、1、1、2、4、2、5、8、2、5、2、6、8、2、4、8、5、7、
0、0、0、1、1、2、4、2、5、8、2、5、2、6、8、2、4、8、5、7、
0、0、0、1、1、2、2、2、2、2、4、5、8、6、8、5、4、8、5、7、
0、0、0、1、1、2、2、2、2、2、4、5、8、6、8、5、4、8、5、7、
0、0、0、1、1、2、2、2、2、2、4、5、8、6、8、5、4、8、5、7、
0、0、0、1、1、2、2、2、2、2、4、5、8、6、8、5、4、8、5、7、
0、0、0、1、1、2、2、2、2、2、4、4、5、6、8、5、8、8、5、7、
0、0、0、1、1、2、2、2、2、2、4、4、5、5、5、6、8、8、8、7、
0、0、0、1、1、2、2、2、2、2、4、4、5、5、5、6、8、8、8、7、
0、0、0、1、1、2、2、2、2、2、4、4、5、5、5、6、7、8、8、8、
0、0、0、1、1、2、2、2、2、2、4、4、5、5、5、6、7、8、8、8、
0、0、0、1、1、2、2、2、2、2、4、4、5、5、5、6、7、8、8、8、
0、0、0、1、1、2、2、2、2、2、4、4、5、5、5、6、7、8、8、8、
0、0、0、1、1、2、2、2、2、2、4、4、5、5、5、6、7、8、8、8、
0、0、0、1、1、2、2、2、2、2、4、4、5、5、5、6、7、8、8、8、
0、0、0、1、1、2、2、2、2、2、4、4、5、5、5、6、7、8、8、8、
0、0、0、1、1、2、2、2、2、2、4、4、5、5、5、6、7、8、8、8、


总结:冒泡排序和快速排序为入门排序,需理解后再尝试编写,希望读此博客者有所收获。

本文来自风马博客原创,如有不对之处请留言指出。




正文到此结束
本文目录