Fork me on GitHub

排序算法学习

发表于 | 分类于 |
| 字数统计 3,048 | 阅读时长 13

总结排序算法

1、比较排序

冒泡排序

基本思想：两两比较相邻记录的关键字，如果反序则交换。
时间复杂度最好为O(n)，最坏的情况是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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
//升序排列
#include<iostream>
#include<vector>
using namespace std;
//两数交换函数
void swap(int &a, int &b)
{
    int tmp = a;
    a = b;
    b = tmp;
}
//基础版
void BubbleSort(vector<int> &array)
{
    for(int i = 0; i < array.size(); i++)
    {
        for(int j = 1; j < array.size(); j++)
        {
            if(array[j-1] > array[j])
            {
                swap(array[j-1], array[j]);
            }
        }
    }
}
//改进版
//思路：记录一轮交换后标记的最后位置，下次从头遍历到这个位置就好。
void BubbleSort_v2(vector<int> &array)
{
    int k;
    int flag = array.size();
    while(flag > 0)
    {
        k = flag;
        flag = 0;
        for(int i = 1; i < k; i++)
        {
            if(array[i-1] > array[i])
            {
                swap(array[i-1], array[i]);
                flag = i;
            }
        }
    }
}

直接插入排序

基本思想：将一个记录插入到已经排好序的有序表中，从而得到一个新的，记录数增加1的有序表。
时间复杂度为O(n^2)，比冒泡和选择排序的性能要更好一些。 稳定性算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream>
#include<vector>
using namespace std;
//直接插入排序
void InsertSort( vector<int> array )
{
    int temp;
    int j;
    for( int i = 1; i < array.size(); i++ )
    {
        temp = array[i];
        for( j = i; j > 0 && array[j-1] > tmp; j-- )
        {
            array[ j ] = array[ j-1 ];
        }
        array[ j ] = tmp;
    }
}

简单选择排序

通过n-i次关键字之间的比较，从n-i+1个记录中选择关键字最小的记录，并和第i（1 <= i<= n）个记录交换值。尽管与冒泡排序同为O（n^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
#include<iostream>
#include<vector>
using namespace std;
//两数交换函数
void swap(int &a, int &b)
{
    int tmp = a;
    a = b;
    b = tmp;
}
//简单选择排序
void simple_select_sort( vector<int> &array )
{
    int min;
    for(int i = 0; i < array.size(); i++)
    {
        min = i;
        for(int j = i+1; j < array.size(), j++)
        {
            if(array[j] < array[min])
            {
                min = j;
            }
        }
        swap(array[i],array[min]);
    }
}

希尔排序

先将整个待排元素序列分割成若干个序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序（增量为1）。其时间复杂度为O（n^(3/2) ),要好于直接插入排序的O(n^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
#include<iostream>
#include<vector>
using namespace std;
//希尔排序
void shell_Sort( vector<int> &array )
{
    int i, j, increment;
    int tmp;
    int N = array.size();
    for( increment = N / 2; increment > 0; increment /=2 )
    {
        for( i = increment; i < N; i++ )
        {
            tmp = array[i];
            for( j = i; j >= increment; j -= increment )
            {
                if( array[j - increment] > tmp )
                {
                    array[j] = array[j - increment];
                }
                else
                {
                    break;
                }
            }
            array[j] = tmp;
        }
    }
}

归并排序

假设初始序列含有n个记录，则可以看成n个有序的子序列，每个子序列的长度为1，然后两两归并，得到（不小于n/2的最小整数）个长度为2或1的有序子序列，再两两归并，……如此重复，直至得到一个长度为n的有序序列为止。这种排序方法称为2路归并排序。时间复杂度为O（nlogn）,空间复杂度为O（n+logn），如果非递归实现归并，则避免了递归时深度为logn的栈空间，空间复杂度为O(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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<iostream>
using namespace std;
/*lpos is the start of left half, rpos is the start of right half*/
void merge(int a[], int tmp_array[], int lpos, int rpos, int rightn)
{
    int i, leftn, num_elements, tmpos;
    leftn = rpos - 1;
    tmpos = lpos;
    num_elements = rightn - lpos + 1;
    /*main loop*/
    while (lpos <= leftn && rpos <= rightn)
        if (a[lpos] <= a[rpos])
            tmp_array[tmpos++] = a[lpos++];
        else
            tmp_array[tmpos++] = a[rpos++];
    while (lpos <= leftn) /*copy rest of the first part*/
        tmp_array[tmpos++] = a[lpos++];
    while (rpos <= rightn) /*copy rest of the second part*/
        tmp_array[tmpos++] = a[rpos++];
    /*copy array back*/
    for (i = 0; i < num_elements; i++, rightn--)
        a[rightn] = tmp_array[rightn];
}
void msort(int a[], int tmp_array[], int left, int right)
{
    int center;
    if (left < right)
    {
        center = (right + left) / 2;
        msort(a, tmp_array, left, center);
        msort(a, tmp_array, center + 1, right);
        merge(a, tmp_array, left, center + 1, right);
    }
}
void merge_sort(int a[], int n)
{
    int *tmp_array;
    tmp_array = (int *)malloc(n * sizeof(int));
    if (tmp_array != NULL)
    {
        msort(a, tmp_array, 0, n - 1);
        free(tmp_array);
    }
    else
        printf("No space for tmp array!\n");
}

堆排序

  • 堆是具有下列性质的完全二叉树：每个节点的值都大于或等于其左右孩子节点的值，称为大顶堆；或者每个节点的值都小于或等于其左右孩子节点的值，称为小顶堆。
  • 堆排序就是利用堆进行排序的方法。基本思想是：将待排序的序列构造成一个大顶堆.此时,整个序列的最大值就是堆顶的根结点.将它移走(其实就是将其与堆数组的末尾元素交换,此时末尾元素就是最大值),然后将剩余的n-1个序列重新构造成一个堆,这样就会得到n个元素的次大值.如此反复执行,便能得到一个有序序列了。时间复杂度为O(nlogn),好于冒泡,简单选择,直接插入的O(n^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
31
32
33
34
35
36
37
38
39
// 构造大顶堆
#define leftChild(i) (2*(i) + 1)
void percDown(int *arr, int i, int N)
{
    int tmp, child;
    for (tmp = arr[i]; leftChild(i) < N; i = child)
    {
        child = leftChild(i);
        if (child != N - 1 && arr[child + 1] > arr[child])
            child++;
        if (arr[child] > tmp)
            arr[i] = arr[child];
        else
            break;
    }
    arr[i] = tmp;
}
void HeapSort(int *arr, int N)
{
    int i;
    for (i = N / 2; i >= 0; i--)
        percDown(arr, i, N);
    for (i = N - 1; i > 0; i--)
    {
        swap1(&arr[0], &arr[i]);
        percDown(arr, 0, i);
    }
}
int main(void)
{
    int arr[] = { 9, 2, 5, 8, 3, 4, 7, 1, 6, 10};
    HeapSort(arr, 10);
    for (int i = 0; i < 10; i++)
        cout << arr[i] << ' ';
    cout << endl;
    return 0;
}

快速排序

对于包含n个数的输入数组，快速排序是一种最坏情况时间复杂度为O(n^2)的排序算法。虽然最坏情况时间复杂度很差，但是快速排序通常是实际排序应用中最好的选择，因为它的平均性能非常好：它的期望时间复杂度为O(nlogn)，而且O(nlogn)中隐含的常数因子非常小。其思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 不稳定性算法。

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
#include<iostream>
#include<vector>
using namespace std;
void swap(int &a, int &b)
{
	int tmp;
	tmp = a;
	a = b;
	b = tmp;
}
int partition(vector<int> &a, int p, int r)
{
	int x = a[r];
	int i = p - 1;
	for (int j = p; j < r; j++)
	{
		if (a[j] <= x)
		{
			i++;
          	if(i == j)
              continue;
			swap(a[i], a[j]);
		}
	}
	swap(a[i + 1], a[r]);
	return i + 1;
}
void quickSort(vector<int> &a, int p, int r) 
//初始调用为quickSort（a, 0, a.size()-1）
{
	int q;
	if (p < r)
	{
		q = partition(a, p, r);
		quickSort(a, p, q-1);
		quickSort(a, q+1, r);
	}
}
int main()
{
	vector<int> a = { 1, 4, 2, 6, 7, 8, 4, 2, 76, 98, 2, 4, 9, 54, 89, 12 };
	int r = a.size() - 1;
	quickSort(a, 0, r);
	for (int i = 0; i < a.size(); i++)
	{
		cout << a[i] << "  ";
	}
	cout << endl;
	getchar();
	return 0;
}

2、非比较排序

非比较排序理论上可以达到O(n),快于比较排序，但是下面三种都是有其应用背景才能发挥作用的，否则使得其反。

计数排序

计数排序(Counting sort)是一种稳定的排序算法。计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。步骤如下：

  • 找出待排序的数组中最大和最小的元素；
  • 统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
  • 对所有的计数累加（从C中的位置为1的元素开始，每一项和前一项相加）；
  • 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1；

由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。

桶排序

桶排序 (Bucket sort)或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。 排序的过程如下：

  • 设置一个定量的数组当作空桶子。
  • 寻访串行，并且把项目一个一个放到对应的桶子去。（hash）
  • 对每个不是空的桶子进行排序。
  • 从不是空的桶子里把项目再放回原来的串行中。

基数排序

基数排序（Radix sort）是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

实现：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。注意，这里必须使用稳定排序，否则，就会让原先的地位排序成果毁于一旦，最终的不到正确的排序结果。

基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。

3、排序算法的稳定性

算法稳定性概念：考察排序算法的时候有一个很重要的特性，就是算法的稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。

算法稳定性的意义

  • 在实际的应用中，我们交换的不一定只是一个整数，而可能是一个很大的对象，交换元素存在一定的开销；
  • 不稳定排序是无法完成基数排序。

4、排序算法的选择

  • 若n较小(如n≤50)，可采用直接插入或直接选择排序。当记录规模较小时，直接插入排序较好；否则因为直接选择移动的记录数少于直接插人，应选直接选择排序为宜。

  • 若文件初始状态基本有序(指正序)，则应选用直接插人、冒泡或随机的快速排序为宜。

  • 若n较大，则应采用时间复杂度为O(nlgn)的排序方法：快速排序、堆排序或归并排序。

    快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；

    堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的；

    若要求排序稳定，则可选用归并排序。但从单个记录起进行两两归并的排序算法并不值得提倡，通常可以将它和直接插入排序结合在一起使用。先利用直接插入排序求得较长的有序子文件，然后再两两归并之。因为直接插入排序是稳定 的，所以改进后的归并排序仍是稳定的。

-------------本文结束感谢您的阅读-------------