【排序】经典排序（待更ing)

🍀 【排序】经典排序（待更ing）

• • 🍁冒泡排序
  • • 算法步骤
    • 动图演示
    • Java代码实现
    • 练习题
  • 🌺快速排序
  • • 算法步骤
    • 动图演示
    • Java代码实现
    • 练习题

🍁冒泡排序

算法步骤

1. 第一轮交换比较相邻的元素。如果第一个比第二个大，就交换他们两个。

2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

3. 重复步骤1和步骤2，第二轮交换找到第二大的元素放在倒数第二位，第三轮交换找到第三大的元素；以此类推

4. 进行到n-1轮交换，交换次小和最小的数，排序完成

动图演示

Java代码实现

public class BubbleSort {public static void main(String[] args) {// TODO Auto-generated method stubint[] array= {29,10,14,37,14,2,5,9};int len=array.length;//记录数组的长度boolean flag;//标志位，若一轮交换的结果为false,说明此轮遍历没有交换元素,数组是已经有序的int swapCount=0;//记录整次排序交换元素的次数for(int i=1;i<len;++i) {//交换n-1轮flag=false;for(int j=0;j<len-i;++j) {//每一轮交换从第一个元素开始,最右侧已经排好序的值无需再遍历if(array[j]>array[j+1]) {int temp=array[j];array[j]=array[j+1];array[j+1]=temp;flag=true;//更新标志位swapCount++;//交换次数加1}}//判断标志位if(flag==false) {break;}////打开这里的注释可以看到每轮交换的结果//System.out.println("第"+(i)+"次交换的结果：");//for(int k=0;k<len;++k) {//System.out.print(array[k]+" ");//}//System.out.println();}System.out.println("一共交换了"+swapCount+"次");for(int i=0;i<len;++i) {System.out.print(array[i]+" ");}}}

结果展示：

第1次交换的结果：10 14 29 14 2 5 9 37 第2次交换的结果：10 14 14 2 5 9 29 37 第3次交换的结果：10 14 2 5 9 14 29 37 第4次交换的结果：10 2 5 9 14 14 29 37 第5次交换的结果：2 5 9 10 14 14 29 37 一共交换了19次2 5 9 10 14 14 29 37 

练习题

HNUCM-OJ问题 A: 例题6-3 冒泡排序

HNUCM-OJ2160: 交换次数

🌺快速排序

快速排序用到了分治的思想

算法步骤

1. 从数列中挑出一个元素，称为 “基准”（pivot）;
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

动图演示

Java代码实现

import java.util.Scanner;public class Main{//输入输出主函数public static void main(String[] args) {// TODO Auto-generated method stubScanner scanner=new Scanner(System.in);int n;int []arr;while(scanner.hasNext()) {n=scanner.nextInt();arr=new int[n];for(int i=0;i<n;++i) {arr[i]=scanner.nextInt();}arr=qSort(arr, 0, n-1);for(int i=0;i<n;++i) {System.out.print(arr[i]);if(i!=n-1) {System.out.print(" ");}}System.out.println();}scanner.close();}//递归求解函数public static int[] qSort(int []arr,int left,int right) {if(left<right) {int pivot=partition(arr,left,right);qSort(arr, left, pivot-1);qSort(arr, pivot+1, right);}return arr;}//划分函数/* * 选取基准元素，将arr[left,right]划分成三段 * arr[left,pivot-1],arr[pivot],arr[pivot+1,right] * arr[pivot]左侧的元素都比arr[pivot]小 * arr[pivot]右侧的元素都比arr[pivot]大 */public static int partition(int []arr,int left,int right) {int pivot=left;int index=pivot+1;for(int i=index;i<=right;++i) {if(arr[i]<arr[pivot]) {swap(arr,i,index);index++;}}swap(arr, pivot, index-1);return index-1;}//交换元素public static void swap(int []arr,int i,int j) {int temp=arr[i];arr[i]=arr[j];arr[j]=temp;} }

练习题

HNUCM-OJ问题 E: 快速排序

j) {
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}

}

 练习题[HNUCM-OJ问题 E: 快速排序](https://acm.hnucm.edu.cn/JudgeOnline/problem.php?cid=1262&pid=4)[HNUCM-OJ问题 F: 随机化快速排序](https://acm.hnucm.edu.cn/JudgeOnline/problem.php?cid=1262&pid=5)