排序算法总结(上)

Author Avatar
Orange 3月 22, 2018
  • 在其它设备中阅读本文章

算法

What’s Algorithm ?

提及“算法”，小白面对高大上说词仰慕之心油然而生 @o@

然而，算法并不神秘 = =

顾名思义，计算方法简称算法（什，什，什，什么！这么简单？→_→）

举个栗子：

从小学就接触的乘法：对 n+n+n+…+n 的简写就是一种算法（递推法^A）,
算法注定要有输入与输出：算式中的 n 即为输入，乘积即为输出。

注：

  • 算法中的状态变化是不确定的
  • 算法必定能在执行有限个步骤之后终止
  • 某些算法加入随机输入，称为随机化算法

How to Assess Algorithm ?

对算法的评定分析主要从时间复杂度(所耗时间长短)与空间复杂度(空间开支大小)来考虑。

关于复杂度的计算需要引入如下渐近记号：

大O记号：

O(g(n)) = { f(n) : 存在正常数c和n0 ，使对所有的n >= n0，都有 0 <= f(n) <= cg(n) }

大Ω记号：

Ω(g(n)) = { f(n) : 存在正常数c和n0 ，使对所有的n >= n0，都有 0 <= cg(n) <= f(n) }

大Θ记号：

Θ(g(n)) = { f(n) : 存在正常数c1和c2和n0 ，使对所有的n >= n0，都有 0 <= c1g(n) <= f(n) <= c2g(n) }

数学证明资料：计算机算法分析之渐进记号

具体计算方式将于实例中给出 ～(~▽~)～

DIY Algorithm ！

以下给出排序算法C++代码：

1.冒泡排序（Bubble Sort）^B

  1. 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
  1. template<typename T>
    void bubbleSort(T arr[],int n)
    {
    	T temp;
    	for(int i = 0;i < n - 1;i++)
    		for(int j = 0;j < n - 1 - i;j++)
    			if(arr[j] > arr[j + 1])
    			{
    				temp = arr[j];
    				arr[j] = arr[j + 1];
    				arr[j + 1] = temp;
    			}
    }

时间复杂度分析：

考虑最坏情况–将逆序数列变为顺序（此情况下，每一次比较都需要进行交换运算） T_T

再举个栗子：数列 5 4 3 2 1 进行冒泡升序排列
第一次外层循环从第一个数5开始到倒数第二个数2结束，
共进行4次比较交换运算，5移到末尾。
第二次外层循环从第一个数4开始到倒数第三个数2结束。
共进行3次比较交换运算，4移到倒数第二个数。
……
依次推类，总比较次数为 4 + 3 + 2 + 1 = 10 次

证明：

根据数学归纳法,对于n位的数列则有比较次数为(n-1) + (n-2) + ... + 1 = n \* (n - 1) / 2 = (n^2 - n) / 2

如图比较次数

若n = 10000，则(n^2 - n) / 2 = (100000000 - 10000) / 2

相对 100000000 来说 10000 微乎其微，故总计算次数约为0.5 \* N^2

用O(N^2)就表示了其数量级（忽略前面系数0.5）

得 冒泡排序的时间复杂度为O(N^2)

  1. 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
  1. //冒泡排序改进版：若遍历中得知数组有序则结束排序
    template<typename T>
    void bubbleSort(T arr[],int n)
    {
    	bool flag = false;
    	T temp;
    	for(int i = 0;i < n - 1;i++)
    	{
    		flag = false;
    		for(int j = 0;j < n - 1 - i;j++)
    			if(arr[j] > arr[j + 1])
    			{
    				flag = true;
    				temp = arr[j];
    				arr[j] = arr[j + 1];
    				arr[j + 1] = temp;
    			}
    		if(flag == false)
    			break;
    	}
    }

改进算法后，对于一个有序数组完成一次外层循环后就会结束，共发生 N - 1 次比较，故升级版冒泡排序在最优情况下的时间复杂度为O(N)

2.插入排序(Insert Sort)

  1. 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
  1. template<typename T>
    void insertSort(T arr[],int n)
    {
    	T temp;
    	for(int i = 1;i < n;i++)
    		if(arr[i] < arr[i - 1])
    		{
    			temp = arr[i];
    			for(int j = i - 1;j >= 0 && arr[j] > temp;j--)
    				arr[j + 1] = arr[j];
    			arr[j + 1] = temp;
    		}
    }

资料：插入排序舞蹈

3.*归并排序（Merge Sort）

  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
    29
    30
    31
    32
    33
  1. template<typename T>
    void mergeSort(T arr[],T temp[],int start,int last)
    {
    	if(start < last)
    	{
    		int mid = (start + last) / 2;
    		mergeSort(arr,temp,start,mid);
    		mergeSort(arr,temp,mid + 1,last);
    		arrUnion(arr,temp,start,mid,last);
    	}	
    }

    template<typename T>
    void arrUnion(T arr[],T temp[],int start,int mid,int last)
    {
    	int i,j,k;
    	i = start;
    	j = mid + 1;
    	k = start;
    	while(i != mid + 1 && j != last + 1)
    	{
    		if(arr[i] < arr[j])
    			temp[k++] = arr[i++];
    		else
    			temp[k++] = arr[j++];
    	}
    	while(i != mid + 1)
    		temp[k++] = arr[i++];
    	while(j != last + 1)
    		temp[k++] = arr[j++];
    	for(i = start;i < last + 1;i++)
    		arr[i] = temp[i];
    }

资料：排序动画演示

Comparison .

下面我们通过这段C语言代码比较排序速度，直观感受时间复杂度。

  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
    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
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    201
    202
    203
    204
    205
    206
    207
    208
    209
    210
    211
    212
    213
    214
    215
    216
    217
    218
    219
    220
    221
    222
    223
    224
    225
    226
    227
    228
    229
    230
    231
    232
    233
    234
    235
    236
    237
    238
    239
  1. #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>

    #define N 5000

    template<typename T>
    void printArr(T arr[],int n);
    template<typename T>
    void quickSort(T arr[],int start,int last);
    template<typename T>
    void quickSortRand(T arr[],int start,int last);
    template<typename T>
    void mergeSort(T arr[],T temp[],int start,int last);
    template<typename T>
    void insertSort(T arr[],int n);
    template<typename T>
    void bubbleSort(T arr[],int n);
    template<typename T>
    void bubbleSortPlus(T arr[],int n);
    template<typename T>
    void choseSort(T arr[],int n);

    int main(int argc, char * argv[])
    {
        clock_t start, end;
        int a[N], b[N], c[N], d[N], e[N], f[N], g[N];
        srand(time(NULL));
        for(int i = 0;i < N;i++)
        {
            g[i] = f[i] = e[i] = d[i] = c[i] = b[i] = a[i] = rand()%100 + rand()%1000;
            //g[i] = f[i] = e[i] = d[i] = c[i] = b[i] = a[i] = N - i;
        }
    	
    	start = clock();
        quickSortRand(a,0,N - 1);
        end = clock();
        printf("随机快速排序用时%lfsec\n",(double)(end - start) / CLOCKS_PER_SEC);
        //printArr(a,N);

    	start = clock();
        quickSort(b,0,N - 1);
        end = clock();
        printf("快速排序用时%lfsec\n",(double)(end - start) / CLOCKS_PER_SEC);
        //printArr(b,N);

        int* temp = (int*)malloc(sizeof(int) * N);
        start = clock();
        mergeSort(c,temp,0,N - 1);
        end = clock();
        printf("归并排序用时%lfsec\n",(double)(end - start) / CLOCKS_PER_SEC);
        //printArr(c,N);
        free(temp);
    	
        start = clock();
        insertSort(d,N);
        end = clock();
        printf("插入排序用时%lfsec\n",(double)(end - start) / CLOCKS_PER_SEC);
        //printArr(d,N);
    	
        start = clock();
        bubbleSort(e,N);
        end = clock();
        printf("冒泡排序用时%lfsec\n",(double)(end - start) / CLOCKS_PER_SEC);
        //printArr(e,N);
    	
        start = clock();
        bubbleSortPlus(f,N);
        end = clock();
        printf("升级版冒泡排序用时%lfsec\n",(double)(end - start) / CLOCKS_PER_SEC);
        //printArr(f,N);
    	
    	start = clock();
        choseSort(g,N);
        end = clock();
        printf("选择排序用时%lfsec\n",(double)(end - start) / CLOCKS_PER_SEC);
        //printArr(g,N);

        return 0;
    }

    template<typename T>
    void quickSort(T arr[],int start,int last)
    {
    	if(start < last)
    	{
    		T temp;
    		int i = start;
    		int j = last;
    		while(i != j)
    		{
    			while(arr[j] >= arr[start] && j != i)
    				j--;
    			while(arr[i] <= arr[start] && i != j)
    				i++;
    			if(i != j)
    			{
    				temp = arr[i];
    				arr[i] = arr[j];
    				arr[j] = temp;
    			}
    		}
    		temp = arr[i];
    		arr[i] = arr[start];
    		arr[start] = temp;
    		quickSort(arr, start, i - 1);
    		quickSort(arr, i + 1, last);
    	}
    }

    template<typename T>
    void quickSortRand(T arr[],int start,int last)
    {
    	if(start < last)
    	{
    		T temp;
    		int i = start;
    		int j = last;
    		int pos = rand() % (last - start) + start;
    		temp = arr[start];
    		arr[start] = arr[pos];
    		arr[pos] = temp;
    		while(i != j)
    		{
    			while(arr[j] >= arr[start] && j != i)
    				j--;
    			while(arr[i] <= arr[start] && i != j)
    				i++;
    			if(i != j)
    			{
    				temp = arr[i];
    				arr[i] = arr[j];
    				arr[j] = temp;
    			}
    		}
    		temp = arr[i];
    		arr[i] = arr[start];
    		arr[start] = temp;
    		quickSortRand(arr, start, i - 1);
    		quickSortRand(arr, i + 1, last);
    	}
    }

    template<typename T>
    void mergeSort(T arr[],T temp[],int start,int last)
    {
        if(start < last)
        {
            int mid = (start + last) / 2;
            mergeSort(arr,temp,start,mid);
            mergeSort(arr,temp,mid + 1,last);
            int i,j,k;
    		i = start;
    		j = mid + 1;
    		k = start;
    		while(i != mid + 1 && j != last + 1)
    		{
    			if(arr[i] < arr[j])
    				temp[k++] = arr[i++];
    			else
    				temp[k++] = arr[j++];
    		}
    		while(i != mid + 1)
    			temp[k++] = arr[i++];
    		while(j != last + 1)
    			temp[k++] = arr[j++];
    		for(i = start;i < last + 1;i++)
    			arr[i] = temp[i];
        }   
    }

    template<typename T>
    void insertSort(T arr[],int n)
    {
        T temp;
        for(int i = 1;i < n;i++)
            if(arr[i] < arr[i - 1])
            {
                temp = arr[i];
                for(int j = i - 1;j >= 0 && arr[j] > temp;j--)
                    arr[j + 1] = arr[j];
                arr[j + 1] = temp;
            }
    }

    template<typename T>
    void bubbleSort(T arr[],int n)
    {
        T temp;
        for(int i = 0;i < n - 1;i++)
            for(int j = 0;j < n - 1 - i;j++)
                if(arr[j] > arr[j + 1])
                {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
    }

    template<typename T>
    void bubbleSortPlus(T arr[],int n)
    {
        bool flag = true;
        T temp;
        for(int i = 0;i < n - 1 && flag;i++)
        {
            flag = false;
            for(int j = 0;j < n - 1 - i;j++)
                if(arr[j] > arr[j + 1])
                {
                    flag = true;
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
        }
    }

    template<typename T>
    void choseSort(T arr[],int n)
    {
    	T temp;
    	for(int i = 0;i < n - 1;i++)
    		for(int j = i + 1;j < n;j++)
    			if(arr[i] > arr[j])
    			{
                    temp = arr[j];
                    arr[j] = arr[i];
                    arr[i] = temp;
    			}
    }

    template<typename T>
    void printArr(T arr[],int n)
    {
        for(int i = 0;i < n;i++)
            printf("%d ", arr[i]);
        printf("\n");
    }

执行条件：

编译程序VC 6.0

数组成员 5000

执行结果：

随机快速排序用时0.001000sec

快速排序用时0.001000sec

归并排序用时0.002000sec

插入排序用时0.033000sec

冒泡排序用时0.090000sec

升级版冒泡排序用时0.089000sec

选择排序用时0.083000sec

下面我们通过这段JAVA语言代码比较排序速度，直观感受时间复杂度。

  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
    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
    76
    77
    78
    79
    80
    81
    82
    83
  1. //Test.java
    package pers.cz.sortcompare;

    import java.util.Random;
    import pers.cz.sortcompare.Sort;

    public class Test {

        public static void main(String[] args) {
            final int n = 1000;
            int[] a = new int[n];
            int[] b = new int[n];
            int[] c = new int[n];
            int[] d = new int[n];
            int[] e = new int[n];
            int[] f = new int[n];
            int[] g = new int[n];
            long start, end;
            Random rand = new Random();
            for (int i = 0; i < a.length; i++) {
                g[i] = f[i] = e[i] = d[i] = c[i] = b[i] = a[i] = rand.nextInt();
            }
            
            start = System.currentTimeMillis();
            Sort.QuickSort(a, 0, n - 1);
            end = System.currentTimeMillis();
            System.out.print("QuickSort cost time(sec):");
            System.out.println(end - start);
            //PrintArrData(a);
            
            start = System.currentTimeMillis();
            Sort.QuickSortRand(b, 0, n - 1);
            end = System.currentTimeMillis();
            System.out.print("QuickSortRand cost time(sec):");
            System.out.println(end - start);
            //PrintArrData(b);
            
            start = System.currentTimeMillis();
            int[] temp = new int[n];
            Sort.MargeSort(c, 0, n - 1, temp);
            temp = null;
            end = System.currentTimeMillis();
            System.out.print("MargeSort cost time(sec):");
            System.out.println(end - start);
            //PrintArrData(c);

            start = System.currentTimeMillis();
            Sort.InsertSort(d);
            end = System.currentTimeMillis();
            System.out.print("InstertSort cost time(sec):");
            System.out.println(end - start);
            //PrintArrData(d);

            start = System.currentTimeMillis();
            Sort.BubbleSortPlus(e);
            end = System.currentTimeMillis();
            System.out.print("BubbleSortPlus cost time(sec):");
            System.out.println(end - start);
            //PrintArrData(e);

            start = System.currentTimeMillis();
            Sort.BubbleSort(f);
            end = System.currentTimeMillis();
            System.out.print("BubbleSort cost time(sec):");
            System.out.println(end - start);
            //PrintArrData(f);
            
            start = System.currentTimeMillis();
            Sort.ChoseSort(g);
            end = System.currentTimeMillis();
            System.out.print("ChoseSort cost time(sec):");
            System.out.println(end - start);
            //PrintArrData(g);

        }

        static void PrintArrData(int[] arr) {
            for (int value : arr) {
                System.out.println(value);
            }
            System.out.println();
        }
    }

  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
    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
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
  1. //Sort.java
    package pers.cz.sortcompare;

    import java.util.Random;

    public class Sort {

        public static void ChoseSort(int[] arr) {
            int temp;
            for (int i = 0; i < arr.length - 1; i++) {
                for (int j = i + 1; j < arr.length; j++) {
                    if (arr[i] > arr[j]) {
                        temp = arr[i];
                        arr[i] = arr[j];
                        arr[j] = temp;
                    }
                }
            }
        }

        public static void BubbleSort(int[] arr) {
            int temp;
            for (int i = 0; i < arr.length - 1; i++) {
                for (int j = 0; j < arr.length - 1 - i; j++) {
                    if (arr[j] > arr[j + 1]) {
                        temp = arr[j];
                        arr[j] = arr[j + 1];
                        arr[j + 1] = temp;
                    }
                }
            }
        }

        public static void BubbleSortPlus(int[] arr) {
            int temp;
            boolean flag = true;
            for (int i = 0; i < arr.length - 1 && flag; i++) {
                flag = false;
                for (int j = 0; j < arr.length - 1 - i; j++) {
                    if (arr[j] > arr[j + 1]) {
                        flag = true;
                        temp = arr[j];
                        arr[j] = arr[j + 1];
                        arr[j + 1] = temp;
                    }
                }
            }
        }

        public static void InsertSort(int[] arr) {
            int j, number;
            for (int i = 1; i < arr.length; i++) {
                if (arr[i] < arr[i - 1]) {
                    number = arr[i];
                    for (j = i - 1; j >= 0 && arr[j] > number; j--) {
                        arr[j + 1] = arr[j];
                    }
                    arr[j + 1] = number;
                }
            }
        }

        public static void MargeSort(int[] arr, int start, int last, int[] temp) {
            if (start < last) {
                int mid = (start + last) / 2;
                Sort.MargeSort(arr, start, mid, temp);
                Sort.MargeSort(arr, mid + 1, last, temp);
                int i, j, k;
                i = start;
                j = mid + 1;
                k = start;
                while (i != mid + 1 && j != last + 1) {
                    if (arr[i] < arr[j]) {
                        temp[k++] = arr[i++];
                    } else {
                        temp[k++] = arr[j++];
                    }
                }
                while (i != mid + 1) {
                    temp[k++] = arr[i++];
                }
                while (j != last + 1) {
                    temp[k++] = arr[j++];
                }
                for (i = start; i < last + 1; i++) {
                    arr[i] = temp[i];
                }
            }
        }

        public static void QuickSort(int[] arr, int start, int last) {
            if (start < last) {
                int temp;
                int i = start;
                int j = last;
                while (i != j) {
                    while (arr[j] >= arr[start] && j != i) {
                        j--;
                    }
                    while (arr[i] <= arr[start] && i != j) {
                        i++;
                    }
                    if (i != j) {
                        temp = arr[i];
                        arr[i] = arr[j];
                        arr[j] = temp;
                    }
                }
                temp = arr[start];
                arr[start] = arr[i];
                arr[i] = temp;
            }
        }

        public static void QuickSortRand(int[] arr, int start, int last) {
            if (start < last) {
                int temp;
                int i = start;
                int j = last;
                Random rand = new Random();
                int pos = rand.nextInt(last - start) + start;
                temp = arr[start];
                arr[start] = arr[pos];
                arr[pos] = temp;
                while (i != j) {
                    while (arr[j] >= arr[start] && j != i) {
                        j--;
                    }
                    while (arr[i] <= arr[start] && i != j) {
                        i++;
                    }
                    if (i != j) {
                        temp = arr[i];
                        arr[i] = arr[j];
                        arr[j] = temp;
                    }
                }
                temp = arr[start];
                arr[start] = arr[i];
                arr[i] = temp;
            }
        }
    }

执行条件：

编译程序NetBeans IDE 8.1

数组成员 1000

执行结果：

QuickSort cost time(sec):1

QuickSortRand cost time(sec):0

MargeSort cost time(sec):1

InstertSort cost time(sec):5

BubbleSortPlus cost time(sec):14

BubbleSort cost time(sec):18

ChoseSort cost time(sec):9

CC许可协议署名非商业性使用相同方式共享
本文采用 CC BY-NC-SA 3.0 Unported 协议进行许可

由 Hexo 强力驱动
Theme - Material