本专栏和大家分享关于排序的算法,其中有插入排（直接插入排序和希尔排序）、选择排序（直接选择排序和堆排）、交换排序（冒泡排序和快速排序）、归并排序以及其他非基于比较的排序
本文与大家分享交换排序
目录
1.冒泡排序
实则就是每次把最大值往后面放,比较简单,我们直接通过代码体现:
public class BubbleSort {
public static void bubbleSort(int[] array){
for(int i = 0; i < array.length - 1; i++){
boolean flg = false;
for(int j = 0; j < array.length - i - 1; j++){
if(array[j] > array[j+1]){
flg = true;
int tmp = array[j+1];
array[j+1] = array[j];
array[j] = tmp;
}
}
if(!flg){
break;
}
}
}
}时空复杂度：
时间复杂度为O(N^2)，最快情况下为O（1）,空间复杂度为O(1)
稳定性:
是稳定的,与选择排序同理
2.快速排序
任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
假设我们的数组是这样的,我们需要先找一个基准(这里以最左边的元素作为基准),那么我们就要想办法把数组变成左边都比6小,右边都比6大的情况
我们采用这种方法:定义变量left,让left 往右走直到遇见一个比6大的数;再定义一个遍历right,让right往左走,直到遇见一个比6小的数,此时交换left和right的元素
然后left++,right--继续按照上面的方式寻找
此时left++和right--后,二者相遇,那么就交换一开始的基准与此时left的值
这样,就能做到左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准
接着,我们开始将区间划分为两部分,两部分再分别进行上述基准的操作...
当我们某一段区间的left和right在一开始就相遇的时候,说明此时就只有一个元素,那么就是有序的了,此时把所有的区间都进行合并就会发现是有序的了
我们先忽略利用基准组织数组的方法(partition),就能把快速排序的框架用代码体现出来,我们可以利用递归来完成,即将将每次划分的区间进行基准组织操作,
那么递归的结束标志是什么呢??
我们看到上面的实例,结束标志是left == right,但是实际上还会出现一种情况:
那么在进行划分操作的时候,right = p-1,此时这种情况下是right < left,左边的递归才结束,因此,我们递归的结束条件是(left >= right)
我们通过代码来呈现大体框架
public static void quickSort(int[] array){
quick(array,0,array.length-1);
}
private static void quick(int[] array,int left,int right){
if(left >= right){
return;
}
int pivot = partition(array,start,right);
quick(array,left,pivot-1);
quick(array,pivot+1,right);
}对于找基准pivot,有多种方法
Hoare法
我们上面的示例用的方法就是Hoare法
即最左边的数作为基准,利用两个变量将数组组织成 左边的数全部小于基准,右边的数全部大于基准的情况,再把此时基准的位置返回,让quick利用基准划分数组
private static int partition(int[] array,int left,int right){
int tmp = array[left];
int i = left;//记录下最左边元素的下标
while(left < right){
while(left < right && array[right] >= tmp){
right--;
}
while(left < right && array[left] <= tmp){
left++;
}
swap(array,left,right);
}
swap(array,i,left);
return left;
}有一个很重要的细节,就是我们一定要让right先找,因为我们最后二者相遇的点一定是小于基准的
如图所示,如果我们让left先找,那么最后left和right都会停在9的位置,就会出问题了
挖坑法
实际上与Hoare相似,但是元素处理方法不同
我们还是以最左边的数作为基准,放到tmp里面,此时与上面不同的是,放到tmp里面后,相当于left这个位置就是"空"了;right先向左走,直到找到一个比6小的,即5,那么就把5放到前面的坑里面,即left的位置:
在left++找到比6大的数,即7,就把7填到right的坑里面,依次类推...直到left和right相遇
private static int partitionHole(int[] array,int left,int right){
int tmp = array[left];
while(left < right){
while(left < right && array[right] >= tmp){
right--;
}
array[left] = array[right];
while (left < right && array[left] <= tmp){
left++;
}
array[right] = array[left];
}
array[left] = tmp;
return left;
}双指针法
实际上用的比较少,重在了解即可,本质就是把所有大于基准值的卷到prev和cur之间,再慢慢往后面卷
private static int partition(int[] array, int left, int right) {
int prev = left ;
int cur = left+1;
while (cur <= right) {
if(array[cur] < array[left] && array[++prev] != array[cur]) {
swap(array,cur,prev);
}
cur++;
}
swap(array,prev,left);
return prev;
}优化
实际上快排的时间复杂度在于能否将数组尽可能均等分,可以的话就时间复杂度就小
如果我们的序列是1 2 3 4 5类似这样的序列,那么按照我们上面的方法来,以最左边的数作为基准,就会出现单分支的情况,那么时间复杂度就很高了,体现不出快排的优势
三数取中法选key
取一段区间内的开头、结尾、中间值，找出三者的中间值作为基准放在首位，这样在进行基准组织就能将每次接近均等划分
private static void quick(int[] array,int start,int end){
if(start >= end){
return;
}
int index = middleNum(array,start,end);
swap(array,index,start);
int pivot = partitionHole(array,start,end);
quick(array,start,pivot - 1);
quick(array,pivot+1,end);
}
private static int middleNum(int[] array,int left,int right){
int mid = left + ((right - left) >> 1);//防止溢出
if(array[left] < array[right]){
if(array[mid] < array[left]) {
return left;
}else if(array[mid] > array[right]){
return right;
}else {
return mid;
}
}else{
if(array[mid] < array[right]) {
return right;
}else if(array[mid] > array[left]){
return left;
}else {
return mid;
}
}
}递归到小的子区间时，可以考虑使用插入排序
private static void quick(int[] array,int start,int end){
if(start >= end){
return;
}
//三数取中
int index = middleNum(array,start,end);
swap(array,index,start);
if(end - start < 5){
insertSort1(array,start,end);
}
int pivot = partitionHole(array,start,end);
quick(array,start,pivot - 1);
quick(array,pivot+1,end);
}
public static void insertSort1(int[] array,int start,int end){
if(array.length == 0){
return;
}
for (int i = start + 1; i <= end; i++) {
int tmp = array[i];
int j = i - 1;
for (; j >= start ; j--) {
if(array[j] < tmp){
array[j + 1] = array[j];
}else{
break;
}
}
array[j + 1] = tmp;
}
}快速排序法非递归实现
实际上就是用栈来模拟递归的过程
public static void quickSortNor(int[] array){
int start = 0;
int end = array.length - 1;
int index = middleNum(array,start,end);
swap(array,index,start);
int pivot = partitionHole(array,start,end);
Stack<Integer> stack = new Stack<>();
if(pivot - 1 > start){
stack.push(pivot - 1 );
stack.push(start);
}
if(pivot + 1 < end){
stack.push(end);
stack.push(pivot + 1);
}
while(!stack.isEmpty()){
start = stack.pop();
end = stack.pop();
pivot = partitionHole(array,start,end);
if(pivot - 1 > start){
stack.push(pivot - 1 );
stack.push(start);
}
if(pivot + 1 < end){
stack.push(end);
stack.push(pivot + 1);
}
}
}时空复杂度:
在平均情况下，快速排序的时间复杂度为O(n log n)，因为每一次递归过程中，将基准元素与其他元素进行比较，将数组分成两部分的时间复杂度为O(n)，而最坏的情况下，每次划分只能减少一个元素，需要进行n次划分，所以最坏情况下的时间复杂度为O(n^2)。
空间复杂度为O(n)
稳定性：不稳定
特点:
快速排序整体的综合性能和使用场景都是比较好的
