发表于 更新于

排序算法

排序的稳定性和时间复杂度，空间复杂度

冒泡排序

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void swap_v(int& a, int& b)
{
	int tmp = a; 
	a = b;
	b = tmp;
}

void sort_v(vector<int>& a)
{
	int tmp;
	for (int i = 0; i < a.size(); i++)
	{
		for (int j = 0; j < a.size()-1; j++)
		{
			if (a[j] < a[j + 1])
			{
				cout << "swapping " << a[j] << " and " << a[j + 1] << endl;
				swap_v(a[j], a[j + 1]);
				cout << "after swap " << a[j] << " and " << a[j + 1] << endl;
			}
		}
	}
}

稳定性强，时间复杂度o(n2),空间复杂度o(1),平均o(n2)

选择排序

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void sort_s(vector<int>& a)
{
	int tmp = 0;
	for (int i = 0; i < a.size(); i++)
	{
		for (int j = i +1; j < a.size(); j++)
		{
			if (a[j] < a[tmp])
			{
				tmp = j;
			}
		}
		cout << "swapping " << a[i] << "  " << a[tmp] << endl;
		swap_v(a[i], a[tmp]);
		cout << "select swapp " << a[i] << "   " << a[tmp] << endl;
	}
}

不稳定性、时间复杂度o(n2),空间复杂度o(1),平均o(n2)

插入排序

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void sort_i(vector<int>& a)
{
	int key;
	for (int i = 1; i < a.size(); i++)
	{
		key = a[i];
		int j=i-1;
		while (j >= 0 && key < a[j])
		{
			/*cout << "swapping j:" << a[j] << "j+1  " << a[j + 1] << endl;*/
			a[j + 1] = a[j];//后移
			j--;
		}
		a[j + 1] = key;
		
		/*cout << "swapping j:" << a[j] << "j+1  " << a[j + 1] << endl;*/
	}
}

稳定性强，时间复杂度o(n2),空间复杂度o(1),平均o(n2)

希尔排序

利用插入排序突破了o(n2)

代码如下:

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
void sort_x(vector<int>& a)
{
	int key;
	int h = 1;
	int n = a.size();
	while (h < n / 3)h = 3 * h + 1;
	while (h >= 1)
	{
		for (int i = h; i < a.size(); i++)
		{
			key = a[i];
			int j = i - h;
			while (j >= 0 && key < a[j])
			{
				/*cout << "swapping j:" << a[j] << "j+1  " << a[j + 1] << endl;*/
				a[j + h] = a[j];//后移
				j=j-h;
			}
			a[j + h] = key;

			/*cout << "swapping j:" << a[j] << "j+1  " << a[j + 1] << endl;*/
		}
		h = h / 3;
	}
}

不稳定，希尔排序空间复杂度o(1)，时间复杂度平均o(1.5)

快速排序

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void quick_sort_v(vector<int>& a, int low, int high)
{
	if (low > high)return;
	int i = low;
	int j = high;
	int key = a[low];
	while (i < j)
	{
		while (i<j && a[j]>=key)
		{
			j--;
		}
		a[i] = a[j];//交换位置
		while (i < j && a[i] =< key)
		{
			i++;
		}
		a[j] = a[i];//交换位置
	}
	a[i] = key;
	quick_sort_v(a, low, i - 1);
	quick_sort_v(a, i + 1, high);
}

稳定，我时间复杂度O(nlog(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
#include <vector>
#include <utility> // std::swap

void heap_sort(std::vector<int>& a) {
    const std::size_t n = a.size();
    if (n < 2) return;

    // 内部下沉：把索引 i 的元素在 [0, heap) 范围内调整成最大堆位置
    auto sift_down = [&](std::size_t i, std::size_t heap) {
        while (true) {
            std::size_t best = i;
            std::size_t L = 2*i + 1, R = L + 1;
            if (L < heap && a[best] < a[L]) best = L;
            if (R < heap && a[best] < a[R]) best = R;
            if (best == i) break;
            std::swap(a[i], a[best]);
            i = best;
        }
    };

    // 建堆（最大堆）
    for (std::size_t i = n/2; i > 0; --i) sift_down(i - 1, n);

    // 依次把堆顶最大换到尾部，缩小堆并下沉修复
    for (std::size_t heap = n; heap > 1; --heap) {
        std::swap(a[0], a[heap - 1]);
        sift_down(0, heap - 1);
    }
}