冒泡排序、快速排序

时间:2022-11-27 15:53:35


冒泡排序、快速排序都属于交换排序,快速排序对冒泡排序优化。

冒泡排序

 

(1)基本思想:在要排序的一组数中,对当前还未排好序的范围内的全部数,自上而下对相邻的两个数依次进行比较和调整,让较大的数往下沉,较小的往上冒。即:每当两相邻的数比较后发现它们的排序与排序要求相反时,就将它们互换。

(2)实例:

冒泡排序、快速排序

(3)用java实现 



  1. public  bubbleSort(){  
  2.      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};  
  3.     int temp=0;  
  4.     for(int i=0;i<a.length-1;i++){  
  5.         for(int j=0;j<a.length-1-i;j++){  
  6.         if(a[j]>a[j+1]){  
  7.             temp=a[j];  
  8.             a[j]=a[j+1];  
  9.             a[j+1]=temp;  
  10.         }  
  11.         }  
  12.     }  
  13.     for(int i=0;i<a.length;i++)  
  14.         System.out.println(a[i]);     
  15. }  
  16. }  



 

 快速排序:

 1、算法概念。

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

2、算法思想。

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

3、实现思路。

①以第一个关键字 K 1 为控制字,将 [K 1 ,K 2 ,…,K n ] 分成两个子区,使左区所有关键字小于等于 K 1 ,右区所有关键字大于等于 K 1 ,最后控制字居两个子区中间的适当位置。在子区内数据尚处于无序状态。 
②把左区作为一个整体,用①的步骤进行处理,右区进行相同的处理。(即递归)
③重复第①、②步,直到左区处理完毕。

4、实现代码。