排序之交换排序：冒泡排序+快速排序

一、冒泡排序

1、思想：从头部开始，两两比较，根据大小交换位置，直到将最大（小）元素放到尾部，对未排序的元素重复此过程。

2、时间复杂度：无论初始序列如何都需多遍扫描

最好：O(N)(带交换旗帜)，正序情况，只有比较时间，无移动时间

最坏：O(N²)，逆序情况

平均：O(N²)

3、辅助空间：O（1）

4、稳定性：稳定

5、适用场合：适合n小的场合

 1 import java.util.*;
 2 
 3 //冒泡排序
 4 public class BubbleSort {
 5     private static Scanner cin;
 6     public static void swap(int a[],int i,int j) {
 7         int temp;//辅助空间O(1)
 8         temp = a[i];
 9         a[i] = a[j];
10         a[j] = temp;
11     }
12     public static void bubbleSort(int[] a) {//从小到大 
13         //两两交换
14         int i,j,flag = 1;//flag为交换旗帜
15         //共n-1趟，除去剩余一个元素（在剩余两个元素时已排号序）
16         for(i = 0;i < a.length-1;i++) {
17             for(j = 0;j<a.length-1-i;j++) {
18                 if(a[j]>a[j+1]) {//变成>=就不稳定，从大到小只需变成<
19                     swap(a,j,j+1);//相邻交换
20                     flag = 0;
21                 }
22             }
23             if(flag == 1) break;//当已排好序则可以跳出  
24         }    
25     }
26     public static  void main(String[] args) {
27         int[] a = new int[5];
28         cin = new Scanner(System.in);
29         int i=0;
30         while(i<a.length) {
31             a[i] =cin.nextInt();
32             i++;
33         }
34         bubbleSort(a);    
35         for(i = 0;i < a.length;i++) {
36             System.out.println(a[i]);
37         }
38     }
39 }

二、快速排序（递归版）

1、思想：对冒泡的改进，采用分治思想，每次将待排元素划分成两部分，通过多次划分过程（过程中变有序即轴点归位），使整个序列变得有序

2、时间复杂度：

最好：O(nlogn)，每次划分都比较平均，轴点接近中央

最坏：O（N²），每次轴点都是最大或最小，导致只划分一个区

平均：O(nlogn)

3、辅助空间：最好情况为O(logn），最坏为O(N)，主要用于递归栈。

4、稳定性：不稳定，交换过程导致

5、适用场合：n较大时

 1 import java.util.Scanner;
 2 
 3 public class QuickSort {
 4     
 5     //找到轴点位置
 6     public static int partition(int[] a,int low,int high) {
 7         int pivotkey = a[low],pivot;
 8         while(low < high) {//相遇停止,交换过程导致不稳定
 9             //从后往前找到比轴点小的数放到前段
10             while(low < high && a[high] >= pivotkey) --high;
11             a[low] = a[high];
12             //从前往后找到比轴点值大的数放到后段
13             while(low < high && a[low] <= pivotkey) ++low;
14             a[high] = a[low];
15         }
16         pivot = low;//记录轴点位置，low = high且为空位
17         a[pivot] = pivotkey;//将轴点值放到正确的位置上
18         return pivot;
19     }
20     
21     public static void quickSort(int[] a,int low,int high) {
22         int pivot;
23         if(low < high) {
24             pivot = partition(a,low,high);
25             quickSort(a, low, pivot-1);//轴点左段
26             quickSort(a, pivot+1, high);//轴点右段
27         }
28     }
29 
30     public static void main(String[] args) {
31         int[] a = new int[10];
32         Scanner cin = new Scanner(System.in);
33         int i=0;
34         while(i<a.length) {
35             a[i] =cin.nextInt();
36             i++;
37         }
38         quickSort(a,0,a.length-1);    
39         for(i = 0;i < a.length;i++) {
40             System.out.print(a[i]+" ");
41         }
42 
43     }
44 
45 }

三、对比

快速排序之所比较快，因为相比冒泡排序，每次交换是跳跃式的。每次排序的时候设置一个基准点，将小于等于基准点的数全部放到基准点的左边，将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换，交换的距离就大的多了。