Search Algorithm

又名顺序查找，从顺序表的一端开始逐个查找关键字是否满足条件，若查找到则查找成功。

1
2
3
4
5
6
7
public static boolean SequenceSearch(int a[], int value){
    for(int i = 0; i < a.length; i++){
        if(a[i] == value) return true;
        else return false;
    }
    return false;
}

优化：引入哨兵机制，新表下边为0位置留空设置值为value 从后往前放在for中查找最后return下标

  • 优点：当n较大时平均查找长度较大效率低。
  • 缺点：对数据元素的存储没有要求，顺序存储或链式存储都可，有序无序都可。
  • 时间复杂度：$O(n)$ 空间复杂度：$O(1)$

重点：仅用于有序的顺序表 可参考LeetCode-704 二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int BinarySearch(int[] nums, int target) {
    int low = 0, high = nums.length - 1;
    while(low <= high){
        int middle = (high - low) / 2 + low;
        int num = nums[middle];
        if(num == target){
            return middle;
        }
        else if(num < target){
            low = middle + 1;
        }
        else{
            high = middle - 1;
        }
    }
    return -1;
}

要点：

  1. 为防止low和high过大溢出 middle = (high - low) / 2 + low
  2. 适合存储结构具有随机存储的特性，仅适用于线性表不适合链式存储结构
  3. 时间复杂度：$O(logn)$ 空间复杂度：$O(1)$

Sort Algorithm

Insertion Sort

直接插入排序

在要排序的一组数中，假定前n-1个数已经排好序，现在将第n个数插到前面的有序数列中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。

稳定性：每次插入元素都是从后向前先比较再移动，所以不会出现相同元素相对位置发生变化的情况，即稳定。

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 static void InsertSort(int array[],int length){
    int temp;
    for(int i=0;i<length-1;i++){
        for(int j=i+1;j>0;j--){
            if(array[j] < array[j-1]){
                temp = array[j-1];
                array[j-1] = array[j];
                array[j] = temp;
            }else{         //不需要交换
                break;
            }
        }
    }
}

// 王道中使用哨兵 array[0]必须空出来
public static void InsertSort(int array[],int length){
    int i, j;
    for(int i = 2; i <= length; i++){
        if(array[i] < array[i-1]){
            array[0] = array[i];
            for(j = i - 1; array[0] < array[j]; --j){
                array[j+1] = array[j];
            }
            array[j+1] = array[0];
        }
    }
}
// for example:
// 0    1    2    3    4 (index)
// null 9    8    7    6
//  8   8    9    7    6
//  7   7    8    9    6
//  6   6    7    8    9

折半插入排序

折半插入相对于直接插入的不同仅仅在于查找元素的时候采用折半查找，查找待插入的元素的插入位置再统一的移动带待插入位置之后的所有元素。只减少了比较元素的次数，稳定。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static void BinaryInsertSort(int[] array){
    int temp;
    for(int i = 1; i < array.length; i++){
        int low = 0;
        int hight = i-1;
        temp = array[i];
        while(high>=low){
            int mid = ( low + high ) / 2;
            if (array[mid] > temp){
                high = mid - 1;
            }else{
                low = mid + 1;
            }
        }
        for (int j = i-1; j > high; j--) {
            array[j+1] = array[j];
        }
        array[hight+1] = temp;
    }
}

希尔排序

先将待排序表分割成若干个形如L[i, i+d, i+2d,...,i+kd]的”特殊”子表，分别进行直接插入排序，当整个表中元素已呈基本有序时，再对全体记录进行一次直接插入排序。

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
public static void ShellSort(int[] arr) {
    int length = arr.length;
    int temp;
    for (int step = length / 2; step >= 1; step /= 2) {//step 步长
        for (int i = step; i < length; i++) {
            temp = arr[i];
            int j = i - step;
            while (j >= 0 && arr[j] > temp) {
                arr[j + step] = arr[j];
                j -= step;
            }
            arr[j + step] = temp;
        }
    }
}

//49 38 65 97 76 13 27 49
//第一趟 d1 = n / 2 = 4
//49          76           子表1   ->   49          76         
//   38          13        子表2   ->      13          38
//      65          27     子表3   ->         27          65
//         97          49  子表4   ->            49          65

//第二趟 d2 = d1 / 2 = 2
//49    27    76    65       ->27    49    65    76
//  13    49    38    97     ->   13    38    49    97

//第三趟 d3 = d2 / 2 = 1
//27 13 49 38 65 49 76 97    ->13 27 38 49 49 65 76 97

Swap Sort

冒泡排序

从后往前或从前往后两两比较相邻元素的大小若逆序就交换，每一趟都有最小的元素交换到待排序列第一个位置。

两个值相等时不会进行交换，所以算法稳定。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static void BubbleSort(int [] arr){
    int temp;//临时变量
    for(int i=0; i<arr.length-1; i++){   //表示趟数，一共arr.length-1次。
        for(int j=arr.length-1; j>i; j--){
            if(arr[j] < arr[j-1]){
                temp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = temp;
            }
        }
    }
}

//9 8 7 6
//9 8 6 7
//9 6 8 7
//6 9 8 7
//6 9 7 8
//6 7 9 8
//6 7 8 9

快速排序

可参考LeetCode-剑指Offer40 最小的k个数

分治法， 划分为独立两部分L[1...k-1] 和 L[k+1...n] 使得前者所有元素小于L(k) 后者所有元素大于L(k)

最后pivot会放在L(k)的位置上，称为一趟快速排序。

  • 从右往左找到第一个比pivot小的数 将high放到low位
  • 从左往右找到第一个比pivot大的数 将low放到high位
  • 将pivot放到low位

若右端有两个关键字相同且均小于pivot的值，其中一个交换到左区间后相对位置改变。不稳定。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public static void QuickSort(int[] arr, int low, int high){
    if(low < high){
        int pivot = Partition(arr, low, high);
        QuickSort(arr, low, pivot-1);
        QuickSort(arr, pivot+1, high);
    }
}

public int Partition(int[] arr, int low, int high){
    int pivot = arr[low];
    while(low < high){
        while(low < high && arr[high] >= pivot) high--;
        arr[low] = arr[high];
        while(low < high && arr[low] <= pivot) low++;
        arr[high] = arr[low];
    }
    arr[low] = pivot;
    return low;
}

//25 84 21 47 15 27 68 35 20
//20 15 21 25 47 27 68 35 84
//15 20 21 25 35 27 47 68 84
//15 20 21 25 27 35 47 68 84

pivot的选择

  1. 固定位置选择基准值

    选取第一个或者最后一个值作为基准值，但是这是一个很不好的处理方法。

    如果序列随机处理时间还可以接受，如果基本有序或者基本倒序快排变冒泡，时间复杂度变$O(n^2)$

  2. 随机选取基准值

    选取待排序列中任意一个值作为基准值，可以让绝大多数数据满足 $O(n\log_2n)$ 的时间复杂度

    1
    2
    3
    4
    Random rand = new Random();
    int index = rand.nextInt(high - low + 1) + low;
    int pivot = nums[index];
    nums[index] = nums[low];

  3. 三数取中法选取基准值

    int a[] = {2,5,4,9,3,6,8,7,1,0};中第一 第(2/n) 最后分别是2,3,0

    三个数中0最小3最大2在中间 所以取2作为基准值

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    int SelectPivotMedianOfThree(int arr[],int low,int high)  
    {  
        int mid = low + ((high - low) >> 1);//计算数组中间的元素的下标  

        //使用三数取中法选择枢轴  
        if (arr[mid] > arr[high])//目标: arr[mid] <= arr[high]  
        {  
            swap(arr[mid],arr[high]);  
        }  
        if (arr[low] > arr[high])//目标: arr[low] <= arr[high]  
        {  
            swap(arr[low],arr[high]);  
        }  
        if (arr[mid] > arr[low]) //目标: arr[low] >= arr[mid]  
        {  
            swap(arr[mid],arr[low]);  
        }  
        //此时，arr[mid] <= arr[low] <= arr[high]  
        return arr[low];  
        //low的位置上保存这三个位置中间的值  
        //分割时可以直接使用low位置的元素作为枢轴，而不用改变分割函数了  
    }

优化方法

序列达到一定大小采用插排

当待排序序列的长度分割到一定大小后，使用插入排序。对于很小和部分有序的数组，快排不如插排好。

由《数据结构与算法分析》Mark Allen Weiness可知，当待排序列长度为5~20之间，此时使用插入排序能避免一些有害的退化情形。

1
2
3
4
5
6
7
8
if (high - low + 1 < 10)  {  
    InsertSort(arr,low,high);  
    return;  
}else{
    pivotPos = Partition(arr,low,high);
    QSort(arr,low,pivotPos-1);
    QSort(arr,pivotPos+1,high);
}
聚集元素

在一次快排分割结束后，将与本次基准相等的元素聚集在一起，再分割时，不再对聚集过的元素进行分割。

具体过程有两步，①在划分过程中将与基准值相等的元素放入数组两端 ②划分结束后，再将两端的元素移到基准值周围

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
//普通过程例如：[7][2][7][1][7][4][7][6][3][8] 由三数取中可得基准为[7]
//第一趟：[7] [2] [3] [1] [6] [4] [7] [7] [7] [8]
//开始聚集元素：
//第一步：[7] [7] [7] [1] [2] [4] [3] [6] [7] [8]
//第二步：[6] [3] [4] [1] [2] [7] [7] [7] [7] [8]
//接下来是对[6] [3] [4] [1] [2] 和 [8]进行快排

public static void QuickSort(int arr[],int low,int high)  
{  
    int first = low;  
    int last = high;  

    int left = low;  
    int right = high;  

    int leftLen = 0;  
    int rightLen = 0;  

    if (high - low + 1 < 10)  
    {  
        InsertSort(arr,low,high);  
        return;  
    }

    //一次分割  
    int key = SelectPivotMedianOfThree(arr,low,high);//使用三数取中法选择枢轴  

    while(low < high)  
    {  
        while(high > low && arr[high] >= key)  
        {  
            if (arr[high] == key)//处理相等元素  
            {  
                swap(arr[right],arr[high]);  
                right--;  
                rightLen++;  
            }  
            high--;  
        }
        arr[low] = arr[high];  
        while(high > low && arr[low] <= key)  
        {  
            if (arr[low] == key)  
            {  
                swap(arr[left],arr[low]);  
                left++;  
                leftLen++;  
            }  
            low++;  
        }
        arr[high] = arr[low];  
    }
    arr[low] = key;  

    //一次快排结束  
    //把与枢轴key相同的元素移到枢轴最终位置周围  
    int i = low - 1;  
    int j = first;  
    while(j < left && arr[i] != key)
    {
        swap(arr[i],arr[j]);  
        i--;  
        j++;  
    }
    i = low + 1;  
    j = last;  
    while(j > right && arr[i] != key)  
    {  
        swap(arr[i],arr[j]);  
        i++;  
        j--;  
    }
    QuickSort(arr,first,low - 1 - leftLen);  
    QuickSort(arr,low + 1 + rightLen,last);  
}
尾递归优化

尾递归原理：

当编译器检测到一个函数调用是尾递归的时候，它就覆盖当前的活动记录而不是在栈中去创建一个新的。编译器可以做到这点，因为递归调用是当前活跃期内最后一条待执行的语句，于是当这个调用返回时栈帧中并没有其他事情可做，因此也就没有保存栈帧的必要了。通过覆盖当前的栈帧而不是在其之上重新添加一个，这样所使用的栈空间就大大缩减了，这使得实际的运行效率会变得更高。

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
40
41
int fact(int n)             //线性递归
{
    if (n < 0)
        return 0;
    else if(n == 0 || n == 1)
        return 1;
    else
        return n * fact(n - 1);
}
 
int facttail(int n, int a)   //尾递归
{
    if (n < 0)
        return 0;
    else if (n == 0)
        return 1;
    else if (n == 1)
        return a;
    else
        return facttail(n - 1, n * a);
}

//线性递归
fact(5)
{5*fact(4)}
{5*{4*fact(3)}}
{5*{4*{3*fact(2)}}}
{5*{4*{3*{2*fact(1)}}}}
{5*{4*{3*{2*1}}}}
{5*{4*{3*2}}}
{5*{4*6}}
{5*24}
120

//尾递归
facttail(5,1)
facttail(4,5)
facttail(3,20)
facttail(2,60)
facttail(1,120)
120
1
2
3
4
5
6
7
8
9
10
11
12
public static void QuickSort(int arr[],int low,int high){
    int pivot;
    if (high - low + 1 < 10){
        InsertSort(arr,low,high);
        return;
    }
    while(low < high){
        pivot = Partition(arr,low,high);
        QuickSort(arr,low,pivot-1);
        low = pivot + 1;
    }
}
多线程处理

分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。

求解这些子问题，然后将各子问题的解合并，从而得到的原问题的解。由此，在处理快排的时候，可以使用多线程提高排序的效率。

Select Sort

简单选择排序

在长度为n的无序数组中，第一次遍历n-1个数，找到最小的数值与第一个元素交换

第二次遍历n-2个数，找到最小的数值与第二个元素交换

直到 第n-1次遍历，找到最小的数值与第n-1个元素交换，排序完成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void SelectSort(int array[],int lenth){
   for(int i=0;i<lenth-1;i++){
       int minIndex = i;
       for(int j=i+1;j<lenth;j++){
          if(array[j]<array[minIndex]){
              minIndex = j;
          }
       }
       if(minIndex != i){
           int temp = array[i];
           array[i] = array[minIndex];
           array[minIndex] = temp;
       }
   }
}

堆排序

可参考LeetCode-剑指Offer40 最小的k个数 Java中堆排序可使用优先队列实现

利用完全二叉树中双亲结点和孩子节点之间的内在关系选择出关键字中最大或最小的元素

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
40
41
//构建最小堆
public static void MakeMinHeap(int a[], int n){
    for(int i=(n-1)/2 ; i>=0 ; i--){
        MinHeapFixdown(a,i,n);
    }
}
//从i节点开始调整,n为节点总数 从0开始计算 i节点的子节点为 2*i+1, 2*i+2  
public static void MinHeapFixdown(int a[],int i,int n){

    int j = 2*i+1; //子节点
    int temp = 0;

    while(j<n){
        //在左右子节点中寻找最小的
        if(j+1<n && a[j+1]<a[j]){  
            j++;
        }

        if(a[i] <= a[j])
            break;

        //较大节点下移
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;

        i = j;
        j = 2*i+1;
    }
}

public static void MinHeapSort(int a[],int n){
    int temp = 0;
    MakeMinHeap(a,n);
    for(int i=n-1;i>0;i--){
        temp = a[0];
        a[0] = a[i];
        a[i] = temp;
        MinHeapFixdown(a,0,i);
    }    
}

建堆时间$O(n)$ 之后有n-1次向下调整操作，每次调整操作时间复杂度都为$O(h) = O(\log_2n)$

故最好最坏平均时间复杂度都为$O(n\log_2n)$

Merge Sort

可参考LeetCode-剑指Offer51 逆序数对

归并：将两个或两个以上的有序表组合成一个新的有序表

假定含有n个记录则可以看成n个有序的子表每个子表长度为1再两两归并

先熟悉如何将两个数组合并到一个数组中：

比较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
public static void MergeSort(int a[],int low, int high){
    if(low < high){
        int mid = (low + high) / 2;
        MergeSort(a, low, mid);
        MergeSort(a, mid+1, high);
        Merge(a, low, mid, high);
    }
}

public void Merge(int a[], int first, int middle, int end){
    //表a的两段a[low...mid]和a[mid+1...high]各自有序，将他们合并成一个有序表
    int[] b = new int[a.length];
    for(int k = low; k <= high; k++){
        b[k] = a[k];
    }
    for(int i = low, j = mid+1, k = i;i <= mid&&j <= high; k++){
        if(b[i] <= b[j]) a[k] = b[i++];
        else a[k] = b[j++];
    }
    while(i <= mid) a[k++] = b[i++];
    while(j <= high) a[k++] = b[i++];
}

//36 20 17 13 28 14 23 15
//20 36|13 17|14 28|15 23
//13 17 20 36|14 15 23 28
//13 14 15 17 20 23 28 36

Radix Sort

利用多关键字的各位大小进行排序，分为最高位优先(MSD)和最低位优先(LSD)两种。

1
2
3
4
5
6
7
8
9
10
# 每位排序：从个位到十位到百位
329        720        720        329
457        355        329        355
657        436        436        436
839   ->   457   ->   839   ->   457
436        657        355        657
720        329        457        720
355        839        657        839

0至9 一共10个关键字 3位数 d=3 r=10
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
public static void RadixSort(int A[],int temp[],int n,int k,int r,int cnt[]){

   //A:原数组
   //temp:临时数组
   //n:序列的数字个数
   //k:最大的位数2
   //r:基数10
   //cnt:存储bin[i]的个数

   for(int i=0 , rtok=1; i<k ; i++ ,rtok = rtok*r){

       //初始化
       for(int j=0;j<r;j++){
           cnt[j] = 0;
       }
       //计算每个箱子的数字个数
       for(int j=0;j<n;j++){
           cnt[(A[j]/rtok)%r]++;
       }
       //cnt[j]的个数修改为前j个箱子一共有几个数字
       for(int j=1;j<r;j++){
           cnt[j] = cnt[j-1] + cnt[j];
       }
       for(int j = n-1;j>=0;j--){      //重点理解
           cnt[(A[j]/rtok)%r]--;
           temp[cnt[(A[j]/rtok)%r]] = A[j];
       }
       for(int j=0;j<n;j++){
           A[j] = temp[j];
       }
   }
}

Performance

排序算法 最好 平均 最差 空间复杂度 稳定性
直接插入排序 $O(n)$ $O(n^2)$ $O(n^2)$ $O(1)$ √
折半插入排序 $O(n)$ $O(n^2)$ $O(n^2)$ $O(1)$ √
希尔排序 $O(n^2)$ $O(1)$ ×
冒泡排序 $O(n)$ $O(n^2)$ $O(n^2)$ $O(1)$ √
快速排序 $O(n\log_2n)$ $O(n\log_2n)$ $O(n^2)$ $O(\log_2n)$ ×
简单选择排序 $O(n^2)$ $O(n^2)$ $O(n^2)$ $O(1)$ ×
堆排序 $O(n\log_2n)$ $O(n\log_2n)$ $O(n\log_2n)$ $O(n)$ ×
二路归并排序 $O(n\log_2n)$ $O(n\log_2n)$ $O(n\log_2n)$ $O(n)$ √
基数排序排序 $O(d(n+r))$ $O(d(n+r))$ $O(d(n+r))$ $O(r)$ √

Reference: 快速排序的四种优化 排序算法总结 十大经典排序算法