前言
今天开始给大家分享数据结构与算法当中十分重要的排序算法，所谓排序，就是将数据元素按指定关键字大小进行升序降序等重新排序，排序是线性表，二叉树等数据结构的一种基本运算，排序它可以提高我们查找的效率，那么接下来就让我们一起进入排序的世界吧
目录
一、交换排序的思想
交换排序的思想：比较两个元素的大小，如果反序，即未按照一定规则进行排序，例如升序，则交换。交换排序有两种算法，一是冒泡排序，二是快速排序。
二、冒泡排序
2.1冒泡排序算法描述
冒泡排序即比较相邻两元素大小，如果反序，则交换，若按照升序排序，则每次应将数据元素序列中最大元素交换到最后位置，即两两相比较，大的元素向后移动，直至将最大的交换到最后的位置，就像水中气泡一样冒出去，得名冒泡排序。
例如，我要将6,5,4,3,2,1这样一组数据按照升序排序，那么第一趟应该是5,4,3,2,1,6,即6和每一个元素比较最终到了最后位置，即符合我们的要求，第二趟就是4,3,2,1,5,6,直到排成了1,2,3,4,5,6则排序结束。
2.2冒泡排序java代码实现
以上述例子为例，我们建一个BubbleSort类，类中定义两个方法，一个swap方法，用于交换数据，一个bubblesort方法用于实现冒泡排序算法。
代码实例
对于代码中的解释我放在注释当中，大家可以自行查看，有不明白的欢迎评论区讨论
Bubble类
package com.Sorting.bubblesort;
/**
* @author wang
* @packageName com.Sorting.bubblesort
* @className Bubble
* @date 2021/11/11 23:24
*/
public class Bubble {
//冒泡排序，升序
public static void bubbleSort(int[] arr) {
//定义一个变量，判断是否有交换
boolean exchange = true;
//双层for循环，外层循环控制是否进行下一次冒泡
for(int i = 1;i<arr.length && exchange;i++) {
//入果下层循环没有进入if语句，说明没有交换存在，外层循环结束
exchange = false;
for(int j = 0;j<arr.length-i;j++) {
//内层循环比较相邻两个元素大小，如果前一个元素大于后一个元素，则调用swap方法两数交换
if(arr[j]>arr[j+1]) {
swap(arr,j,j+1);
//发生交换
exchange = true;
}
}
}
}
public static void swap(int[] arr,int i,int j) {
//交换两个数据
int temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
}测试类：
package com.Sorting.bubblesort;
import java.util.Arrays;
/**
* @author wang
* @packageName com.Sorting.bubblesort
* @className BubbleTest
* @date 2021/11/11 23:39
*/
public class BubbleTest {
public static void main(String[] args) {
int [] arr = {6,2,4,3,5,1};
Bubble.bubbleSort(arr);
System.out.println(Arrays.toString(arr));
}
}
/*
输出结果
[1, 2, 3, 4, 5, 6]
*/2.3冒泡排序算法分析
冒泡排序我们分析他的两种情况：
1.最好情况：数据序列排序，那么只进行一次冒泡，比较n此，时间复杂度为O(n).
2.最坏情况：数据反序排列或者随机排列，那么数据就会进行n-1此冒泡， 因为我们最后一趟冒泡n已经排好，所以我们要进行n-1此冒泡，大家可以自行画图理解。比较次数和移动次数都是（n-1）+(n-2) +.....+2+1；最后可以得到其时间复杂度为O(n2)。那么我们的冒泡排序即在越接近有序的情况下，他的算法的时间效率就越高，反之，如果我的数据有成千上万个，且刚好反序，那么我的效率就十分的低了。因此，冒泡排序虽然稳定，但是也难免会造成效率低下。那么接下来我们就可以学习另一种高级一点的排序方式，快速排序。
三、快速排序
3.1快速排序算法描述
在数据序列中选择一个元素作为基准值，每趟从数据序列的两端开始交替进行，将小于基准值的元素交换到序列前端，将大于基准值的元素交换到序列后端，介于两者之间的位置则成为基准位置的最终位置，同时，序列将会被划分成为两个子序列，分别对两个子序列进行快速排序，直到子序列长度为1，则完成排序。
那么我们通过图来理解
首先我们有一组数组int[] arr = {6,1,2,3,8,9,4,5,7};
目前数组这样排序，我们可以给定一个low指针，来指向数组中第一个元素，high指针来指向最后一个元素，首先我们先比较high的值7与基准元素的值6，发现7大于6，就将high的位置向左移动，直到high的值小于或等于基准元素的值，比如5时，我们交换5与6，使得high位置的值为6，low位置的值为5；接下来从low位置向右开始找，找到元素比基准元素值小，例如5,1,2,3,均比基准元素6小，那么我们就将low的值移动到直到8，这时，8>6,那么应该将8与6的位置交换，因为，大的元素始终在右边，小的元素始终在右边（升序排序），接下来我们就会得到这样一个结果
这时我们的low与high还是不相等，说明排序还没有完成，继续将high的值与左边的值相比较，一样的道理，high值与基准元素比较，如果大于6，high的值向左进，low的值与其比较，如果小于，则向右进，排序完结果如下，
当我们在继续进行下一次排序循环时，结果如下：
这时我们的 low值与high值已经相等，我们就退出循环，这时第一趟排序就已经完成，我们发现其实此时的数组并未按照升序进行排序，此时就需要调用递归对基准元素左边数组，右边数组分别进行以上排序，递归进行排序就可以了。那么java版代码实现如下
3.2快速排序代码实现
package com.Sorting.quickSort;
/**
* @author wang
* @packageName com.Sorting.quickSort
* @className QSort
* @date 2021/11/16 22:57
*/
public class QSort {
public static void main(String[] args) {
int[] arr = {6,1,2,3,8,9,4,5,7};
QuickSort(arr,0,arr.length-1);
for(int i : arr) {
System.out.print(i + " ");
}
//输出结果：1 2 3 4 5 6 7 8 9
}
public static void QuickSort(int[] arr,int low,int high) {
int pivot;
if(low<high) {
pivot = partition(arr,low,high);
//对基准值左边数组进行排序，基准值减一即从索引0处的值到基准值前一个元素参与下一次排序
QuickSort(arr,low,pivot-1);
//同理，对基准值右边数组进行递归排序，从基准值后一个元素到最后一个元素的值进行排序
QuickSort(arr,pivot+1,high);
}
}
public static int partition(int[] arr,int low,int high) {
//记录一个关键值，例如数组中第一个元素
int pivotKey = arr[low];
//当low的位置小于high的位置时，循环结束
while(low<high) {
//当high处的值大于基准位置的值时，进入循环，当其值小于基准值时，退出循环
while(low<high && arr[high] >= pivotKey) {
high--;
}
//退出循环后，应该将此时的high的值和low处的值交换，也就是将high处的值与基准值进行交换
swap(arr,low,high);
//与上面同理
while(low<high && arr[low] <= pivotKey) {
low++;
}
swap(arr,low,high);
}
//返回关键字所在位置，这里返回low，high皆可，因为当low==high循环结束
return low;
}
public static void swap(int[] arr,int i,int j) {
//交换两个数据
int temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
}
3.3快速排序算法总结
快速排序算法因为关键字的比较和交换是跳跃进行的，因此，快速排序算法是不稳定的。当待排序序列元素较多且数据元素随机排列时，快速排序是相当快速的；当待排序序列元素较多且基准值选择不合适时，快速排序则较慢。
最后，欢迎大家在评论区提出一些建议，文中可能有不少表述较为不清晰的地方，欢迎大家结合图以及代码来阅读，最后，恳求大家路过时给个小小的点赞，下期还会继续为大家带来一些java小知识哦，再见！