冒泡排序、快速排序都属于交换排序,快速排序对冒泡排序优化。
冒泡排序
(1)基本思想:在要排序的一组数中,对当前还未排好序的范围内的全部数,自上而下对相邻的两个数依次进行比较和调整,让较大的数往下沉,较小的往上冒。即:每当两相邻的数比较后发现它们的排序与排序要求相反时,就将它们互换。
(2)实例:
(3)用java实现
- public bubbleSort(){
- int a[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,56,17,18,23,34,15,35,25,53,51};
- int temp=0;
- for(int i=0;i<a.length-1;i++){
- for(int j=0;j<a.length-1-i;j++){
- if(a[j]>a[j+1]){
- temp=a[j];
- a[j]=a[j+1];
- a[j+1]=temp;
- }
- }
- }
- for(int i=0;i<a.length;i++)
- System.out.println(a[i]);
- }
- }
快速排序:
1、算法概念。
2、算法思想。
通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
3、实现思路。
①以第一个关键字 K 1 为控制字,将 [K 1 ,K 2 ,…,K n ] 分成两个子区,使左区所有关键字小于等于 K 1 ,右区所有关键字大于等于 K 1 ,最后控制字居两个子区中间的适当位置。在子区内数据尚处于无序状态。
②把左区作为一个整体,用①的步骤进行处理,右区进行相同的处理。(即递归)
③重复第①、②步,直到左区处理完毕。
4、实现代码。