常用排序算法整理及代码实现

Posted on Edited on

本文对我编写的常用的排序算法进行整理和总结，方便用时进行查阅和参考。

快速排序

快速排序是实际应用中的最好选择，采用了分治法的思想。通过一趟排序将待排序记录分割成独立的两部分，其中一部分的关键字均比另外一部分的小，分别对这两部分记录进行排序，已达到整个有序。

是否稳定：不稳定

时间复杂度：O(nlogn)

空间复杂度：O(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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <stdio.h>
#include <vector>
#include <iostream>

int partition(std::vector<int> &numbers, int low, int high)
{
    int pivotkey = numbers[low];
    while (low < high)
    {
        while (low < high && numbers[high] >= pivotkey)
        {
            --high;
        }
        numbers[low] = numbers[high];
        while (low < high && numbers[low] <= pivotkey)
        {
            ++low;
        }
        numbers[high] = numbers[low];
        numbers[low] = pivotkey;
    }
    return low;
}


void quick_sort(std::vector<int> &numbers, int low, int high)
{
    if (low < high)
    {
        int pivotloc = partition(numbers, low, high);
        quick_sort(numbers, low, pivotloc - 1);
        quick_sort(numbers, pivotloc + 1, high);
    }
}

void quick_sort(std::vector<int> &numbers)
{
    quick_sort(numbers, 0, numbers.size() - 1);
}

int main()
{
    std::vector<int> numbers = {49, 38, 65, 97, 76, 13, 27, 49};
    quick_sort(numbers);
    for (int i=0; i<numbers.size(); i++)
    {
        printf("%d\t", numbers[i]);
    }
    printf("\n");
}

归并排序

将两个或两个以上的有序表组合成一个新的有序表。合并两个有序表的方法为：比较两个有序表中第一个数，谁小先取谁。继续进行比较，只要有一个有序表为空，直接将另一个有序表取出即可。

是否稳定：稳定

时间复杂度：O(nlogn)

空间复杂度：O(n) （当使用顺序存储时，为了能够实现两个有序表之间的合并），或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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
/**
 * 归并排序使用递归算法的效率比较低，具体应用中会采用非递归算法代替
 */
void merge(std::vector<int> &numbers, std::vector<int> &extra, int low, int high, int middle)
{
    int i = low, j = middle+1, k = low;
    for (; i<=middle && j<=high; k++)
    {
        if (numbers[i] <= numbers[j])
        {
            extra[k] = numbers[i];
            i++;
        }
        else
        {
            extra[k] = numbers[j];
            j++;
        }
    }
    
    while (i <= middle)
    {
        extra[k++] = numbers[i++];
    }

    while (j <= middle)
    {
        extra[k++] = numbers[j++];
    }

    for (int m = low; m <= high; m++)
    {
        numbers[m] = extra[m];
    }
}


void merge_sort(std::vector<int> &numbers, std::vector<int> &extra, int low, int high)
{
    if (low == high)
    {
        return ;
    }
    int middle = (low + high) / 2;
    merge_sort(numbers, extra, low, middle);
    merge_sort(numbers, extra, middle + 1, high);
    merge(numbers, extra, low, high, middle);
}

void merge_sort(std::vector<int> &numbers)
{
    // 申请额外的存储空间来用于排序处理
    std::vector<int> extra = numbers;
    merge_sort(numbers, extra, 0, numbers.size() - 1);
}

int main()
{
    std::vector<int> numbers = {49, 38, 65, 97, 76, 13, 27, 49};
    merge_sort(numbers);

    for (int i=0; i<numbers.size(); i++)
    {
        printf("%d\t", numbers[i]);
    }
    printf("\n");
}

链式存储代码

以下为采用链式存储结构的代码，本答案为我在LeetCode上的Sort List 题目的答案，源码放在我的Github上。

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
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

/**
 * 使用归并排序方法，核心思想为将数组拆分为两半，分别对两半进行排序，排序完成后再进行一次排序，排序算法就可以采用插入排序的方式。
 * 对两半排序的算法仍然采用归并排序算法，即问题为递归问题
 * 在使用线性存储结果的归并排序算法中，会使用额外的空间来存储临时结果，空间复杂度为O(n)，而在链式存储中，空间复杂度为O(1)
 * 归并排序的时间复杂度为O(nlogn)
 * 如果存储结构为双向链表，可以使用快速排序
 */
ListNode* sortList(ListNode* head)
{
    if (head == nullptr || head->next == nullptr)
    {
        return head;
    }

    if (head->next->next == nullptr)
    {
        // 仅有两个元素，对两个元素进行排序后直接返回
        if (head->val < head->next->val)
        {
            return head;
        }
        else
        {
            ListNode *tmp = head->next;
            tmp->next = head;
            tmp->next->next = nullptr;
            return tmp;
        }
    }

    // 为了找到中间节点，这里采用快慢指针的方式，否则需要使用先遍历一次取长度，然后找到中间位置的两次遍历方式
    ListNode *fast = head;
    ListNode *slow = head;
    ListNode *slow_prev = nullptr;
    while (fast != nullptr && fast->next != nullptr)
    {
        fast = fast->next->next;
        slow_prev = slow;
        slow = slow->next;
    }
    fast = slow_prev->next;
    slow_prev->next = nullptr;

    // 分别对两段链表进行排序
    slow = sortList(head);
    fast = sortList(fast);

    // 对两段链表进行合并
    ListNode *node = nullptr, *result = nullptr;
    while (slow != nullptr && fast != nullptr)
    {
        if (slow->val < fast->val)
        {
            if (result != nullptr)
            {
                node->next = slow;
                node = node->next;
            }
            else
            {
                node = slow;
                result = slow;
            }
            slow = slow->next;
        }
        else
        {
            if (result != nullptr)
            {
                node->next = fast;
                node = node->next;
            }
            else
            {
                node = fast;
                result = fast;
            }
            fast = fast->next;
        }
    }
    if (slow != nullptr)
    {
        node->next = slow;
    }

    if (fast != nullptr)
    {
        node->next = fast;
    }

    return result;
}

直接插入排序

该排序算法的时间复杂度为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
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

void insertion_sort(std::vector<int> &numbers)
{
	if (numbers.size() <= 1)
	{
		return;
	}
	for (int i = 1; i < numbers.size(); i++)
	{
		for (int j = i; j > 0; j--)
		{
			if (numbers[j] < numbers[j - 1])
			{
				swap(numbers[j], numbers[j - 1]);
			}
			else
			{
				break;
			}
		}
	}
}

int main()
{
	int a[] = { 49, 38, 65, 97, 76, 13, 27, 49 };
	vector<int> numbers(a, a + sizeof(a) / sizeof(int));
	insertion_sort(numbers);
	for (int i = 0; i<numbers.size(); i++)
	{
		printf("%d\t", numbers[i]);
	}
	return 0;
}

链式存储代码

以下代码为LeetCode上的链式存储的情况时的直接插入排序算法的代码。

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
ListNode* insertionSortList(ListNode* head) 
{
    if (head == NULL)
    {
        return NULL;
    }
    
    // 初始化
    ListNode *node = head->next;
    ListNode *new_head = head;
    new_head->next = NULL;
    while (node != NULL)
    {
        ListNode *node_next = node->next;   // 先将当前遍历的下一个节点保存
        
        // 将当前节点插入到新链表中
        ListNode *new_node_tmp = new_head;
        if (node->val < new_node_tmp->val)
        {
            // 当前节点插入新链表的第一个位置
            node->next = new_head;
            new_head = node;
        }
        else
        {
            // 将当前节点插入到中间
            while (new_node_tmp->next != NULL)
            {
                if (node->val < new_node_tmp->next->val)
                {
                    node->next = new_node_tmp->next;
                    new_node_tmp->next = node;
                    break;
                }
                new_node_tmp = new_node_tmp->next;
            }
            
            // 将该节点插入到最后位置
            if (new_node_tmp->next == NULL)
            {
                new_node_tmp->next = node;
                node->next = NULL;
            }
        }
            
        // 开始遍历当前节点的下一个节点
        node = node_next;
    }
    return new_head;
}