各种排序算法

排序算法比较
排序算法比较

快速排序

快排

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
public void quicksort(int[] arr, int low, int high) {
     if (low < high) {//这里要判断
         //先找出pivot
         int pivot = partition(arr, low, high);
         //分别排序
         quicksort(arr, low, pivot);
         quicksort(arr, pivot + 1, high);
     }
 }
 private int partition(int arr[], int low, int high) {
     //每次都要和flag进行比较
     int flag = arr[low];
     while (low < high) {
         while (low < high && arr[high] >= flag) {
             high--;
         }
         //交换low和high的位置
         swap(arr, low, high);
         while (low < high && arr[low] <= flag) {
             low++;
         }
         swap(arr, low, high);
     }
     //返回的是下标
     return low;
 }

双轴快排

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Partitioning:
 left part           center part                   right part
+--------------------------------------------------------------+
|  < pivot1  |  pivot1 <= && <= pivot2  |    ?    |  > pivot2  |
+--------------------------------------------------------------+
             ^                          ^       ^
             |                          |       |
            less                        k     great
Invariants:
            all in (left, less)   < pivot1
  pivot1 <= all in [less, k)     <= pivot2
            all in (great, right) > pivot2
Pointer k is the first index of ?-part.

一般的快速排序采用一个枢轴来把一个数组划分成两半，然后递归之。
大量经验数据表面，采用两个枢轴来划分成3份的算法更高效，这就是DualPivotQuicksort。
动画：https://learnforeverlearn.com/yaro_web/
http://www.tuicool.com/articles/BfY7Nz

bfprt

Median of medians
时间复杂度O(N)
其精髓是选择pivot，不是任意的选,
而是选择中位数中的中位数-Median of medians
步骤：
5个数分一组，分为n/5一组
组内插入排序，选择所有的上中位数，单独组成一个数组arrm[]
求所有中位数的中位数，即arrm[]的中位数，使用递归调用，求出次中位数pivot
然后快排使用pivot来划分区域，看k是否是中间区域
http://blog.duyaokeep.cn/2015/11/05/5.2/

堆排序

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
public void heapsort(int[] arr) {
    //初次建堆
    //这里是以0开头的数组，因此最后一个非子节点是arr.length / 2 - 1，如果序号是1就是arr.length / 2
    for (int i = arr.length / 2 - 1; i >= 0; i--) {
        heapy(arr, i, arr.length);
    }
    //每次堆排都把最大的放在0的位置，然后把排好的放在最后
    for (int i = arr.length - 1; i > 0; i--) {
        swap(arr, 0, i);
        heapy(arr, 0, i);
    }
}
private void heapy(int[] arr, int parent, int len) {
     //每次都和这个值比较，即使parent变化
     int tmp = arr[parent];
     int child = parent * 2 + 1;
     while (child < len) {
         if (child + 1 < len && arr[child] < arr[child + 1]) {
             child++;
         }
         if (tmp > arr[child]) {
             break;
         }
         arr[parent] = arr[child];
         parent = child;
         child = parent * 2 + 1;
     }
     //因为上面已经将父节点下移，所以tmp相当于与给子节点赋值了
     arr[parent] = tmp;
 }

初次建立堆的过程是O(n)，heapy的过程是O(logn)
堆排总的时间复杂度是O(nlogn)因为一共n个数字每个数字都要堆化heapyO(logn)

归并排序

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
31
32
33
34
public void mergesort(int[] arr, int low, int high) {
    //仍然要加条件
    if (low < high) {
        int mid = low + (high - low) / 2;
        mergesort(arr, low, mid);
        mergesort(arr, mid + 1, high);
        mergeArray(arr, low, mid, high);
    }
}
private void mergeArray(int[] arr, int low, int mid, int high) {
    int[] tmp = new int[high - low + 1];
    int cnt = 0;
    int i = low, j = mid + 1;
    while (i <= mid && j <= high) {
        if (arr[i] < arr[j]) {
            tmp[cnt++] = arr[i];
            i++;
        } else {
            tmp[cnt++] = arr[j];
            j++;
        }
    }
    while (i <= mid) {
        tmp[cnt++] = arr[i++];
    }
    while (j <= high) {
        tmp[cnt++] = arr[j++];
    }
    for (cnt = 0; cnt + low <= high; cnt++) {
        arr[cnt + low] = tmp[cnt];
    }
}

基数排序

又称为桶排序，将数字按照位数拆分为若干个关键字，每次对一位进行排序

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
31
32
33
34
35
36
37
38
39
public void radixSort(int[] array) {
      int max = array[0];
      for (int i = 0; i < array.length; i++) {  //找到数组中的最大值
          if (array[i] > max) {
              max = array[i];
          }
      }
      int keysNum = 0;  //关键字的个数，我们使用个位、十位、百位...当做关键字，所以关键字的个数就是最大值的位数
      while (max > 0) {
          max /= 10;
          keysNum++;
      }
      List<ArrayList<Integer>> buckets = new ArrayList<ArrayList<Integer>>();
      for (int i = 0; i < 10; i++) {  //每位可能的数字为0~9，所以设置10个桶
          buckets.add(new ArrayList<Integer>());  //桶由ArrayList<Integer>构成
      }
      for (int i = 0; i < keysNum; i++) {  //由最次关键字开始，依次按照关键字进行分配
          for (int j = 0; j < array.length; j++) {  //扫描所有数组元素，将元素分配到对应的桶中
              //取出该元素对应第i+1位上的数字，比如258，现在要取出十位上的数字，258%100=58,58/10=5
              int key = array[j] % (int) Math.pow(10, i + 1) / (int) Math.pow(10, i);
              buckets.get(key).add(array[j]);  //将该元素放入关键字为key的桶中
          }
          //分配完之后，将桶中的元素依次复制回数组
          int counter = 0;  //元素计数器
          for (int j = 0; j < 10; j++) {
              ArrayList<Integer> bucket = buckets.get(j);  //关键字为j的桶
              while (bucket.size() > 0) {
                  array[counter++] = bucket.remove(0);  //将桶中的第一个元素复制到数组，并移除
              }
          }
      }
  }

其它排序

冒泡排序http://blog.csdn.net/u012152619/article/details/47305859
选择排序http://blog.csdn.net/u012152619/article/details/47306053
插入排序http://blog.csdn.net/u012152619/article/details/47306209