【数据结构】7大基于比较的排序（冒泡排序、快速排序、归并排序）

Bertha 。 2024-04-18 13:45 39阅读 0赞

## 五.冒泡排序 ##

思想：冒泡排序就是两个相邻的元素之间进行比较，把最大的冒到最后，一般是比较好理解的

//冒泡排序
 public static void bubbleSort(int [] array){
 for(int i=0;i<array.length-1;i++){
 boolean treated=true;
 for(int j=0;j<array.length-i-1;j++){
 if(array[j]>array[j+1]){
 swap(array,j,j+1);
 treated=false;
 }
 }
 if(treated==true){
 break;
 }
 }
 }

## 六.快速排序 ##

其基本思想为：任取待排序元素序列中 的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

分割的过程：四种方法

1）左右往中间靠

a.hover b.挖坑法

2）前后遍历

a,前后遍历 b.把基准值单独处理

//快速排序
 public static void quickSort(int [] array){
 quickSortInternal(array,0,array.length-1);
 }
 public static void quickSortInternal(int [] array,int left,int right){
 if(left>=right){
 return;
 }
 //1.确定基准值：array[right]作为基准值
 //2.遍历，小的在左，大的在右
 //int pivotIndex1=partioion1(array,left,right);
 //int pivotIndex2=partioion2(array,left,right);
 //int pivotIndex3=partition3(array,left,right);
 int [] indices=partition4(array,left,right);
 //分出两个小区间
 //[left,pivotlndex-1]
 //[pivotlndex+1,right]
 //quickSortInternal(array,left,pivotIndex1-1);
 //quickSortInternal(array,pivotIndex1+1,right);
 //quickSortInternal(array,left,pivotIndex2-1);
 //quickSortInternal(array,pivotIndex2+1,right);
 //quickSortInternal(array,left,pivotIndex3-1);
 //quickSortInternal(array,pivotIndex3+1,right);
 quickSortInternal(array,left,indices[0]-1);
 quickSortInternal(array,indices[1]+1,right);
 }
 public static int partioion1(int [] array,int left,int right){
 int pirot=array[right];
 int great=right;
 int less=left;
 while(less<great){
 while(less<great&&array[less]<=pirot){
 less++;
 }
 while(less<great&&array[great]>=pirot){
 great--;
 }
 swap(array,less,great);
 }
 swap(array,less,right);
 return less;
 }
 public static int partioion2(int []array,int left,int right){
 int pirot=array[right];
 int great=right;
 int less=left;
 while (less < great) {
 while(less<great&&array[less]<=pirot){
 less++;
 }
 array[great]=array[less];
 while(less<great&&array[great]>=pirot){
 great--;
 }
 array[less]=array[great];
 }
 array[less]=pirot;
 return less;
 }
 public static int partition3(int [] array,int left,int right){
 int less=left;
 int pirot=array[right];
 for(int i=left;i<right;i++){
 if(array[i]<pirot){
 swap(array,i,less);
 less++;
 }
 }
 swap(array,less,right);
 return less;
 }
 public static int [] partition4(int [] array,int left,int right){
 int pirot=array[right];
 int great=right;
 int i=left;
 int less=left;
 while(i<great){
 if(array[i]==pirot){
 i++;
 }
 if(array[i]<pirot){
 swap(array,i,less);
 i++;
 less++;
 }
 else{
 while(i<great&&array[great]>pirot){
 great--;
 }
 swap(array,i,great);
 }
 }
 return new int [] {less,great-1};
 }

非递归的做法：

自己只用栈记录，待排序区间的左右边界

再利用分割的方法

//快速排序非递归
 public static void quickSortNoR(int [] array){
 Stack<Integer> stack=new Stack<>();
 stack.push(array.length-1);
 stack.push(0);
 while(!stack.isEmpty()){
 int left=stack.pop();
 int right=stack.pop();
 if(left>=right){
 continue;
 }
 int pivotIndex=partition(array,left,right);
 //[left,pivotIndex-1]
 //[pivotIndex+1,right]
 stack.push(right);
 stack.push(pivotIndex+1);
 stack.push(pivotIndex-1);
 stack.push(left);
 }
 }

## 七.归并排序 ##

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有 序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

具体实现：

合并两个有序数组的过程

0.平均切分待排序区间，如果待排序区间的左右两个小区间已经有序，则，按照合并有序数组的方法，使最终区间有序

1.先找到中间位置，化分左右两个小区间，直到小区间长度==1或者<1

2.分治的思想，先排左右两个小区间

3.合并有序数组

//归并排序
 //左闭右开
 public static void mergeSort(int [] array){
 mergeSortInternal(array,0,array.length);
 }
 public static void mergeSortInternal(int[] array, int low, int high) {
 if(low+1>=high){
 return;
 }
 int mid=(high+low)/2;
 //[low,mid)
 //[mid,high)
 mergeSortInternal(array,low,mid);
 mergeSortInternal(array,mid,high);
 merge(array,low,mid,high);
 }
 //合并两个数组
 public static void merge(int [] array,int low,int mid,int high){
 int length=high-low;
 int [] extra=new int [length];
 int iLeft=low;
 int iRight=mid;
 int iExtra=0;
 while(iLeft<mid&&iRight<high){
 if(array[iLeft]<=array[iRight]){
 extra[iExtra++]=array[iLeft++];
 }
 if(array[iLeft]>array[iRight]){
 extra[iExtra++]=array[iRight++];
 }
 }
 while(iLeft<mid){
 extra[iExtra++]=array[iLeft++];
 }
 while(iRight<high){
 extra[iExtra++]=array[iRight++];
 }
 for(int i=0;i<length;i++){
 array[low+i]=extra[i];
 }
 }

非递归的做法：

先使数组中的每个元素为一个区间，然后两两合并为一个区间，再以合并好的区间为一个区间，再两两合并，如下图所示

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjY5MDA3_size_16_color_FFFFFF_t_70][]

//非递归归并排序
 public static void mergeSortNoR(int [] array){
 for(int i=1;i<array.length;i=i*2){
 for(int j=0;j<array.length;j=j+2*i){
 int low=j;
 int mid=j+i;
 int high=mid+i;
 if(mid>=array.length){
 continue;
 }
 if(high>array.length){
 high=array.length;
 }
 merge(array,low,mid,high);
 }
 }
 }

最后，对七种排序进行总结：

<table style="width:555px;"> 
 <tbody> 
 <tr> 
 <td style="width:96px;">排序方法</td> 
 <td style="width:101px;">平均时间复杂度</td> 
 <td style="width:97px;">最好时间复杂度</td> 
 <td style="width:88px;">最坏时间复杂度</td> 
 <td style="width:91px;">空间复杂度</td> 
 <td style="width:79px;">稳定性</td> 
 </tr> 
 <tr> 
 <td style="width:96px;">直接插入排序</td> 
 <td style="width:101px;">O(n^2)</td> 
 <td style="width:97px;">O(n)</td> 
 <td style="width:88px;">O(n^2)</td> 
 <td style="width:91px;">O(1)</td> 
 <td style="width:79px;">稳定</td> 
 </tr> 
 <tr> 
 <td style="width:96px;">希尔排序</td> 
 <td style="width:101px;"> O(n^1.3~1.4) </td> 
 <td style="width:97px;">O(n)</td> 
 <td style="width:88px;">O(n^2)</td> 
 <td style="width:91px;">O(1)</td> 
 <td style="width:79px;">不稳定</td> 
 </tr> 
 <tr> 
 <td style="width:96px;">简单选择排序</td> 
 <td style="width:101px;"> O(n^2) </td> 
 <td style="width:97px;"> O(n^2) </td> 
 <td style="width:88px;"> O(n^2) </td> 
 <td style="width:91px;">O(1)</td> 
 <td style="width:79px;">不稳定</td> 
 </tr> 
 <tr> 
 <td style="width:96px;">堆排序</td> 
 <td style="width:101px;"> O(n*log(n)) </td> 
 <td style="width:97px;"> O(n*log(n)) </td> 
 <td style="width:88px;"> O(n*log(n)) </td> 
 <td style="width:91px;">O(1)</td> 
 <td style="width:79px;">不稳定</td> 
 </tr> 
 <tr> 
 <td style="width:96px;">冒泡排序</td> 
 <td style="width:101px;">O(n^2)</td> 
 <td style="width:97px;">O(n)</td> 
 <td style="width:88px;">O(n^2)&nbsp;</td> 
 <td style="width:91px;">O(1)</td> 
 <td style="width:79px;">稳定</td> 
 </tr> 
 <tr> 
 <td style="width:96px;">快速排序</td> 
 <td style="width:101px;"> O(n*log(n)) </td> 
 <td style="width:97px;"> O(n*log(n)) </td> 
 <td style="width:88px;">O(n^2)</td> 
 <td style="width:91px;">O(log(n)~O(n))</td> 
 <td style="width:79px;">不稳定</td> 
 </tr> 
 <tr> 
 <td style="width:96px;">归并排序</td> 
 <td style="width:101px;"> O(n*log(n)) </td> 
 <td style="width:97px;"> O(n*log(n)) </td> 
 <td style="width:88px;"> O(n*log(n)) </td> 
 <td style="width:91px;">O(n)</td> 
 <td style="width:79px;">稳定</td> 
 </tr> 
 </tbody> 
</table>

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjY5MDA3_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/ff6aca2e7a8e44e49938e5aefbb2df42.png