冒泡排序

基本原理

通过对相邻元素两两比较，根据大小来交换元素的位置，通过一趟趟的比较和交换，最终得到一个有序的数组。原始的冒泡排序是稳定排序。由于该排序算法的每一轮要遍历所有元素，轮转的次数和元素数量相当，所以时间复杂度是$O(N^2)$

冒泡排序

,,

基本冒泡排序算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class BubbleSort{
    private static void sort(int array[]){
        int tmp=0;
        for(int i=0;i<array.length-i-1;j++)
        {
            if(array[j]>array[j]){
                tmp=array[j];
                array[j]=array[j+1];
                array[j+1]=tmp;
            }
        }
    }
}
public static void main(String[] args){
    int[] array=new int[]{5,8,6,3,9,2,1,7};
    sort(array);
    System.out.println(Arrays.toString(array));
}

冒泡排序优化版

上个版本存在的问题，如果执行到最后三轮的时候，发现整个数列已经是有序的了，可以按上面的代码执行的话算法还是仍然“兢兢业业”地继续执行第七轮、第八轮。如果我们能判断出数列已经有序，并且做出标记，剩下的几轮排序就可以不必执行，提早结束工作。其实也很简单，就是将上面代码做一点点小小改动即可，也就是利用布尔变量 isSorted作为标记。如果在本轮排序中，元素有交换，则说明数列无序；如果没有元素交换，说明数列已然有序，直接跳出大循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static int[] bubbleSort(int[] arr) {
     if (arr == null || arr.length < 2) {
          return arr;
     }
    for (int i = 0; i < arr.length - 1; i++) {
         boolean isSorted  = true;//有序标记，每一轮的初始是true
         for (int j = 0; j < arr.length -i - 1; j++) {
             if (arr[j + 1] < arr[j]) {
                 isSorted  = false;//有元素交换，所以不是有序，标记变为false
                 int t = arr[j];
                 arr[j] = arr[j+1];
                 arr[j+1] = t;
             }
         }
         //一趟下来是否发生位置交换，如果没有交换直接跳出大循环
         if(isSorted )
              break;
     }
     return arr;
}

冒泡排序升级版

如果数列中前半部分是无序的，后半部分是有序的呢？比如（3，4，2，1，5，6，7，8）这个数组，其实后面的许多元素已经是有序的了，但是每一轮还是白白比较了许多次。对于的问题，关键在于对这数列有序区的界定。如果按冒泡排序代码原始版来分析的话，有序区的长度和排序的轮数是相等的。比如第一轮排序过后的有序区长度是1，第二轮排序过后的有序区长度是2 ……。
但是呢，实际数列真正的有序区可能会大于这个长度，也就是上面这个例子，第二轮中后面 5 个实际上都已经属于有序区了。因此后面的比较是没有意义的了。
我们可以这样做来避免这种情况：在每一轮排序的最后，记录一下最后一次元素交换的位置，那个位置也就是无序数列的边界，再往后就是有序区了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public static int[] bubbleSort(int[] arr) {
     if (arr == null || arr.length < 2) {
          return arr;
     }
    //记录最后一次交换的位置
    int lastExchangeIndex = 0;
    //无序数列的边界，每次比较只需要比到这里为止
    int sortBorder = arr.length - 1;
    
    for (int i = 0; i < arr.length - 1; i++) {
         boolean isSorted  = true;//有序标记，每一轮的初始是true
         for (int j = 0; j < sortBorder; j++) {
             if (arr[j + 1] < arr[j]) {
                 isSorted  = false;//有元素交换，所以不是有序，标记变为false
                 int t = arr[j];
                 arr[j] = arr[j+1];
                 arr[j+1] = t;
                 lastExchangeIndex = j;
             }
         }
        sortBorder = lastExchangeIndex
         //一趟下来是否发生位置交换，如果没有交换直接跳出大循环
         if(isSorted )
              break;
     }
     return arr;
}

选择排序

原理

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。时间复杂度为$O(n^2)$;空间复杂度为$O(1)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class MySorts {
    public static void main(String[] args) {
        int[] arr = new int[]{23,20,32,5,45,6,8,9,15,1};
        selectionSort(arr);
        System.out.println("排序结果："+ Arrays.toString(arr));
    }

    private static void selectionSort(int[] arr) {
        for(int i=0;i<arr.length-1;i++){
            int minIndex = i;//最小数位置
            for(int j=i;j<arr.length-1;j++){
                if(arr[j+1]<arr[minIndex]){
                    minIndex = j+1;
                }
            }
            //内循环结束说明找到了最小数位置
            if(minIndex != i){
                swapReferences(arr,minIndex,i);
            }
        }
    }

    private static void swapReferences(int[] arr, int minIndex, int i) {
        int tmp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = tmp;
    }
}

插入排序

插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void print(int a[], int n ,int i){
  cout<<i <<":";
  for(int j= 0; j<8; j++){
    cout<<a[j] <<" ";
  }
  cout<<endl;
}
void InsertSort(int a[], int n)
{
  for(int i= 1; i<n; i++){
    if(a[i] < a[i-1]){   //若第i个元素大于i-1元素，直接插入。小于的话，移动有序表后插入
      int j= i-1;
      int x = a[i];     //复制为哨兵，即存储待排序元素
      a[i] = a[i-1];           //先后移一个元素
      while(x < a[j]){   //查找在有序表的插入位置
        a[j+1] = a[j];
        j--;     //元素后移
      }
      a[j+1] = x;     //插入到正确位置
    }
    print(a,n,i);      //打印每趟排序的结果
  }

}

int main(){
  int a[15] = {2，3,4,5,15，19，16，27，36，38，44，46，47，48，50};
  InsertSort(a,15);
  print(a,15,15);
}

鸡尾酒排序——冒泡Plus

希尔排序

快速排序

归并排序

堆排序

计数排序

桶排序

基数排序

排序算法总结

排序算法 平均时间复杂度 最差时间复杂度 空间复杂度 数据对象稳定性
冒泡排序 $O(n^2)$ $O(n^2)$ $O(1)$ 稳定
选择排序 $O(n^2)$ $O(n^2)$ $O(1)$ 数组稳定，链表不稳定
插入排序 $O(n^2)$ $O(n^2)$ $O(1)$ 稳定
快速排序 $O(n*log_{2}n)$ $O(n^2)$ $O(log_{2}n)$ 不稳定
堆排序 $O(n*log_{2}n)$ $O(n*log_{2}n)$ $O(1)$ 不稳定
归并排序 $O(n*log_{2}n)$ $O(n*log_{2}n)$ $O(n)$ 稳定
希尔排序 $O(n*log_{2}n)$ $O(n^2)$ $O(1)$ 不稳定
计数排序 $O(n+m)$ $O(n+m)$ $O(n+m)$ 稳定
桶排序 $O(n)$ $O(n)$ $O(m)$ 稳定
基数排序 $O(k*n)$ $O(n^2)$ 稳定