[数据结构与算法] 排序算法之冒泡排序与快速排序(快排)
冒泡排序法
冒泡排序（Bubble Sorting）的基本思想是：
- 通过对待排序序列从前向后（从下标较小的元素开始）,依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就象水底下的气泡一样逐渐向上冒。
- 因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此要在排序过程中设置一个标志flag判断元素是否进行过交换。从而减少不必要的比较。(这里说的优化，可以在冒泡排序写好后，在进行)
思路图
由思路图可知
- 一共执行数组长度-1 次大循环
- 每次大循环的作用是通过两两进行比较, 将本次循环中最大的元素移到后面, 直到所有循环移动完毕
- 优化: 通过布尔变量flag进行优化,默认为false ,如果发生数据的交换就将flag置为true,并在每次循环结束将flag初始化为false; 如果没有发生数据交换说明该数组数据有序,则直接退出当前循环
代码实现
注意: 两种方法时间复杂度都是 n^2
package ah.sz.tp.algorithm1.sort;
import java.util.Arrays;
/**
* 冒泡排序法(正序,时间复杂度n^2)
*
* @author TimePause
* @create 2020-01-31 11:46
*/
public class BubbleSort {
public static void main(String[] args) {
int[] arr = {3, 9, -1, 10, 20};
//int[] arr = {1,2,3,4,5,6};//测试冒泡排序改良是否正确
bubbleSort2(arr);
System.out.println(Arrays.toString(arr));
}
/**
* 冒泡排序法
* 1.需要n-1次大循环
* 2.每个大循环需要比较n-i-1次,作用是将当前循环的一个最大值传到右边
* 3.如果逆序,交换其值;如果都是顺序则直接输出排序结果
*
* @param arr
*/
public static void bubbleSort(int[] arr){
// 用于交换数据的临时变量
int temp=0;
for (int i=0;i<arr.length-1;i++){
for (int j=0;j<arr.length-1-i;j++){
// 正序排序,如果前一个元素大于后一个元素则交换位置
if (arr[j]>arr[j+1]){
temp = arr[j+1];
arr[j+1] = arr[j];
arr[j] = temp;
}
}
/*System.out.println("第"+(i+1)+"次排序效果如下");
System.out.println(Arrays.toString(arr));*/
}
}
/**
* 冒泡排序法优化-使用flag
* 1.需要n-1次大循环
* 2.每个大循环需要比较n-i-1次,作用是将当前循环的一个最大值传到右边.例如数组长度为5,第一次循环需要比较4次,第二次并比较需要3次...以此类推
* 3.如果逆序,交换其值;如果都是顺序则直接输出排序结果
*
* @param arr
*/
public static void bubbleSort2(int[] arr){
// 用于交换数据的临时变量
int temp=0;
// 用于标识是否发生了交换
boolean flag=false;
for (int i=0;i<arr.length-1;i++){
for (int j=0;j<arr.length-1-i;j++){
// 正序排序,如果前一个元素大于后一个元素则交换位置
if (arr[j]>arr[j+1]){
// 如果逆序, true
flag=true;
temp = arr[j+1];
arr[j+1] = arr[j];
arr[j] = temp;
}
}
/* System.out.println("第"+(i+1)+"次排序效果如下");
System.out.println(Arrays.toString(arr));*/
if (!flag){//如果flag为false,说明没有发生交换
break;
}else {
//如果发生了交换,需要将flag重新置为false, 防止其在下一个循环异常结束
flag=false;
}
}
}
}冒泡排序的另一种方法
- 每次令i与j 的关系都是 j=i+1 (相邻)
- 每个循环都是将下标为 i 的元素,i 后面的所有元素相比较, 将最大的移到后面
public static void bubbo(int[] arr) {
int temp = 0;
for (int i = 0; i < arr.length; i++) {
for (int j = i + 1; j < arr.length; j++) {
if (arr[i] > arr[j]) {
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
}快速排序法
- 快速排序（Quicksort）是对冒泡排序的一种改进。
- 基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列
快速排序法应用实例:
- 要求: 对 [-9,78,0,23,-567,70] 进行从小到大的 排序，要求使用快速排序法。【测试8w和800w】 说明[验证分析]: 如果取消左右递归，结果是 -9 -567 0 23 78 70 如果取消右递归,结果是 -567 -9 0 23 78 70 如果取消左递归,结果是 -9 -567 0 23 70 78
public class QuickSort {
// 时间复杂度 O(nlogn)
public static void quickSort(int[] arr, int left ,int right){
int l= left;//左下标
int r = right;//右下标
int pivot =arr[(left+right)/2];//中轴值
int temp=0;//辅助变量,交换数据时使用
//while循环的作用是让比pivot值小的放在左边,比pivot值大的放在右边
while (l<r){
// 在pivot的左边一直找, 找到大于等于pivot的值才退出
// 作用是找到不符合条件的元素,进行元素交换
while (arr[l]<pivot){
l+=1;//作用是一直找
}
// 在pivot的右边一直找, 找到小于pivot的值才退出
while (arr[r]>pivot){
r -= 1;
}
//如果l>=r,说明指针已经从左边移动找pivot,或者它的右边.因此pivot的左右两的值,已按照规律排序
//即: 左边都是小于pivot的值, 右边都是大于pivot的值
if (l>=r){
break;
}
//交换元素
temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
//如果交换完后，发现这个arr[l] == pivot值 相等 r--， 前移
if(arr[l] == pivot) {
r -= 1;
}
//如果交换完后，发现这个arr[r] == pivot值 相等 l++， 后移
if(arr[r] == pivot) {
l += 1;
}
}
// 如果 l == r, 必须l++, r--, 否则为出现栈溢出
if (l == r) {
l += 1;
r -= 1;
}
//向左递归
if(left < r) {
quickSort(arr, left, r);
}
//向右递归
if(right > l) {
quickSort(arr, l, right);
}
}
public static void main(String[] args) {
int[] arr = {-9, 78, 0, 23, -567, 70};
quickSort(arr,0,arr.length-1);
System.out.println(Arrays.toString(arr));
}
}测试8w数据排序,用时约为1s以内; 800w数据排序,用时3s左右, 优于希尔排序
举报
腾讯云开发者
