必须掌握的八种排序（5-6）--冒泡排序，快速排序

本文主要是介绍必须掌握的八种排序（5-6）--冒泡排序，快速排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

5、冒泡排序

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

（2）理解图

这里写图片描述

（3）代码实现

/*** 冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，* 如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，* 也就是说该数列已经排序完成。* 这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。* 步驟：*    1、比较相邻的元素。如果第一个比第二个大，就交换他们两个。2、对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。3、针对所有的元素重复以上的步骤，除了最后一个。4、持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。* @author Administrator**/
public class bubbleSort {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]);}
}

6、快速排序

（1）基本思想：选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描，将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。

（2）理解图

这里写图片描述

（3）代码实现

public static void quickSort(int [] a,int left,int right){//快速排序算法   //找一个基准元素,把数组分为两个部分,前面一部分比基准元素小  后面一部分比基准元素大 保证前面一部分的元素都小于后面一部分的元素//一般以第一个元素作为基准元素//找两个助手 ,低助手和高助手  ,分别位于数组的两端//低助手从左往右找比基准元素大的元素 找到则交换 记录该位置 找不到的话 低助手索引加1//高助手从右往前找比基准元素小的元素，找到则交换 ，记录该位置，找不到的话，低助手索引减1//直到低助手和高助手重叠 ,则记录该位置   ,数组就被分成了两个部分 再对这两部分进行递归,再分成两部分  最后合即为排好序的数组if(left==right){return;}int partition=partition(a,left,right);//递归quickSort(a,left,partition);quickSort(a,partition+1,right);}  /*** 找中间位置的方法* @param a 待排序数组* @param left ：低助手   低助手从左往右找比基准元素大的元素 找到则交换 记录该位置 找不到的话 低助手索引加1* @param right: 高助手  高助手从右往前找比基准元素小的元素，找到则交换 ，记录该位置，找不到的话，低助手索引减1*/public static int partition(int [] a,int left,int right){int base=a[left];//找两个助手 ,低助手和高助手  ,分别位于数组的两端left--;right++;while(left<right){left++;while(a[left]<base){left++;}right--;while(a[right]>base){right--;}if(left<right){swap(a,left,right);}}return right;}//交换值的函数public static  void swap(int [] a,int i,int j){int temp;temp=a[i];a[i]=a[j];a[j]=temp;}