交换排序(冒泡排序、快速排序)

雨点打透心脏的1/2处 2022-11-27 15:45 220阅读 0赞

## 1、冒泡排序 ##

### 1.1、概念 ###

冒泡排序是通过对排序序列从前向后(从下标较小的元素开始)、依次比较相邻元素的值，若发现逆序则交换，使较大的元素逐渐从前移向后部，就像水底的气泡一样逐渐向上冒。

### 1.2、基本思想 ###

1.  设有n个待排序的记录。首先将第一个记录的值和第二个记录的值进行比较，如果逆序,则交换两个值。然后比较第二记录和第三个记录的值。依次类推，直至第n-1个记录和第n个记录的值进行比较为止。上述过程称作第一趟起泡排序，其结果使得值最大的记录被安置到最后一个记录的位置上。
2.  然后进行第二趟起泡排序，对前n-1个记录进行同样操作，其结果是使值次大的记录被安置到第n-1个记录的位置上。
3.  重复上述比较和交换过程，第i趟是从i到n-i+1依次比较两个记录的值，并在"逆序"时交换相邻记录，其结果是这n-i+1个记录中值最大的记录被交换到第n-i+1的位置上。直到在某一趟排序过程中没有进行过交换值的操作，说明序列已经全部达到排序要求，则完成排序。

### 1.3、举例分析 ###

以3,9,-1,10,20，这组包含5个值的数据为例进行分析  
第一趟排序：3,-1,9,10,20  
第二趟排序：-1,3,9,10,20  
第三趟排序：-1,3,9,10,20  
第四趟排序：-1,3,0,10,20  
我们可以看出5个数进行了4趟排序，第一趟排序对3到20这5个数依次两两比较逆序则交换得出最大的数20，共比较4次；第二趟排序对3到10这4个数依次两两比较逆序则交换得出最大的数10，共比较3次；第三趟排序对-1到9这三个数依次两两比较逆序则交换得出最大的数9，共比较2次；第四趟排序对-1到3这两个数比较得出最大的值3，共比较1次。  
我们可以得出如果有n个数，需要排序n-1趟，每趟的比较次数是这次需要比较的数值总数-1

### 1.4、代码实现 ###

从1.3中可以看出第二趟排序-1和3进行了交换，此时已经是有序的了，第三趟排序没有进行任何值位置的交换，为了使程序不再进行第4趟排序，下面代码使用变量flag进行控制。

public class BubbleSort {
        
     public static void main(String[] args) {
        
         int[] arr ={
        3,9,-1,10,20};
         bubbleSort(arr);
         System.out.println(Arrays.toString(arr));
     }
     public static void bubbleSort(int[] arr){
        
         int temp = 0;//临时变量
         boolean flag = false;//标识变量，表示是否进行过交换
         //变量i控制比较的趟数，此例长度为5，需比较次数4次i取值：[0,4)
         for(int i=0;i<arr.length-1;i++){
        
             //变量j控制每趟依次需要两两比较的次数，是这次比较值的数量-1
             //每趟比较前减去一个数(上一趟排序后得出来的最大的数)，第一趟比较减去0，依次减去1、2、3
             for(int j=0;j<arr.length-i-1;j++){
        
                 if(arr[j]>arr[j+1]){
        
                     flag=true;
                     temp=arr[j];
                     arr[j]=arr[j+1];
                     arr[j+1]=temp;
                 }
             }
             if (!flag){
        
                 //在一趟排序中，一次交换都没用发生过（说明数组内值已经是有序的了）
                 break;
             }else{
        
                 flag=false;//重置flag,进行下次判断
             }
         }
     }
    }

### 1.5、时间复杂度空间复杂度 ###

1.  时间复杂度  
    最好情况（初始序列为正序）：只需要进行一趟排序，在排序过程中进行n-1次值的比较，且不移动。  
    最坏情况（初始序列为逆序）：需进行n-1趟排序，总的值比较次数KCN和记录移动次数RMN(每次交换都要移动3次记录)分别是：  
    KCN=  ∑ i = n 2 ( i − 1 ) = 1 + 2 + 3 + . . . . . . n − 1 = n ( n − 1 ) 2 ≈ n 2 2 \\sum \_\{i=n\}^\{2\}(i-1) =1+2+3+......n-1=\\frac\{n(n-1)\}\{2\}≈\\frac\{n^2\}\{2\} ∑i=n2(i−1)=1\+2\+3\+......n−1=2n(n−1)≈2n2  
    RMN=  3 ∑ i = n 2 ( i − 1 ) = 3 ( 1 + 2 + 3 + . . . . . . n − 1 ) = 3 n ( n − 1 ) 2 ≈ 3 n 2 2 3\\sum \_\{i=n\}^\{2\}(i-1) =3(1+2+3+......n-1)=\\frac\{3n(n-1)\}\{2\}≈\\frac\{3n^2\}\{2\} 3∑i=n2(i−1)=3(1\+2\+3\+......n−1)=23n(n−1)≈23n2  
    所以，在平均情况下，冒泡排序关键字的比较次数和记录移动次数分别约为  n 2 / 4 n^2/4 n2/4和  3 n 2 / 4 3n^2/4 3n2/4,时间复杂度为O( n 2 n^2 n2)
2.  空间复杂度  
    冒泡排序只有在两个记录交换位置时需要一个辅助空间做暂存记录，所以空间复杂度为O(1)。

### 1.6、算法特点 ###

1.  是稳定排序。
2.  可用于链式存储结构。
3.  移动记录次数较多，算法平均时间性能比直接插入排序差。当初始记录无序，n较大时，此算法不宜采用。

## 2、快速排序 ##

### 2.1、概念 ###

快速排序是对**冒泡排序**的一种改进。在冒泡排序过程中，只对相邻的两个记录进行比较，因此每次交换两个相邻记录时只能消除一个逆序。如果能通过两个(不相邻)记录的一次交换，消除多个逆序，则会大大加快排序的速度。快速排序方法中的一次交换可能消除多个逆序。快速排序，通过一趟排序将要排序的数据分割成独立的两个部分，其中一部分的所有数据都比另一部分的所有数据都要小，然后再按照此方法对这两部分数据分别进行快速排序，**整个排序过程可以递归进行**，以此达到整个数据变成有序序列。

### 2.2、基本思想 ###

1.  在待排序的n个记录中任取一个记录(我这里取数组的中间值)，作为**枢轴**pivot。经过第一趟排序后，把所有小于pivot值的记录交换到前面，把所有大于pivot值的记录交换到后面，结果将待排序记录分为两个子表，现在枢轴在分界处位置。然后，分别对左、右子表重复上述过程，直至每一个子表只有一个记录时，排序完成。
2.  其中，一趟快速排序的具体做法如下：  
    （1）附设两个下标l和r,初始时分别指向表的下界和上界设枢轴记录的值为pivot(第一趟，left=0;right=arr.length-1)。  
    （2）从表的最右侧位置，依次向左搜索找到第一个值小于pivot的记录。具体操作：当left<right时，若right所指记录的值大于等于pivot,则向左移动下标right;。  
    （3）然后再从表的最左侧位置，依次向右搜索找到第一个值大于pivot的记录。具体操作：当left<right时，若left所指记录的值小于等于pivot,则向右移动下标left;  
    （4）将左边大于pivot和右边小于pivot的值进行交换  
    （4）重复步骤（2）、（3）、（4），直至left和right相等为止。

### 2.3 、代码实现 ###

public class QuickSort {
        
    public static void main(String[] args) {
        
         int[] arr={
        -9,78,0,23,-567,70};
         quickSort(arr,0,arr.length-1);
         System.out.println("arr="+ Arrays.toString(arr));
     }
     public static void quickSort(int[] arr,int left,int right){
        
         int l=left;//左下标
         int r=right;//右下标
         //pivot 枢轴
         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值
             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);
         }
     }
    }

### 2.4、时间复杂度和空间复杂度 ###

1.  时间复杂度:O( n l o g 2 n nlog2^n nlog2n)
2.  空间复杂度:O( l o g 2 n log2^n log2n)

### 2.5、 算法特点 ###

1.  记录非顺次地移动导致排序方法是不稳定的。
2.  排序过程中需要定位表的下界和上界，所以适合用于顺序结构，很难用于链式结构。
3.  当n较大时，在平均情况下快速排序是所有内存排序方法中速度最快的一种，所以其适合初始记录无序、n较大时的情况。