数据排序 第2课时

1.桶排序

本页面将简要介绍桶排序。

定义

桶排序（英文：Bucket sort）是排序算法的一种，适用于待排序数据值域较大但分布比较均匀的情况。

过程

桶排序按下列步骤进行：

  1. 设置一个定量的数组当作空桶；
  2. 遍历序列，并将元素一个个放到对应的桶中；
  3. 对每个不是空的桶进行排序；
  4. 从不是空的桶里把元素再放回原来的序列中。

性质

稳定性

如果使用稳定的内层排序，并且将元素插入桶中时不改变元素间的相对顺序，那么桶排序就是一种稳定的排序算法。

由于每块元素不多，一般使用插入排序。此时桶排序是一种稳定的排序算法。

时间复杂度

桶排序的平均时间复杂度为 O(n + n^2/k + k)（将值域平均分成 n块 + 排序 + 重新合并元素），当 k\approx n 时为 O(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
28
29
30
31
32
const int N = 100010;
int n, w, a[N];
vector<int> bucket[N];
void insertion_sort(vector<int>& A) {
  for (int i = 1; i < A.size(); ++i) {
    int key = A[i];
    int j = i - 1;
    while (j >= 0 && A[j] > key) {
      A[j + 1] = A[j];
      --j;
    }
    A[j + 1] = key;
  }
}

void bucket_sort() {
  int bucket_size = w / n + 1;
  for (int i = 0; i < n; ++i) {
    bucket[i].clear();
  }
  for (int i = 1; i <= n; ++i) {
    bucket[a[i] / bucket_size].push_back(a[i]);
  }
  int p = 0;
  for (int i = 0; i < n; ++i) {
    insertion_sort(bucket[i]);
    for (int j = 0; j < bucket[i].size(); ++j) {
      a[++p] = bucket[i][j];
    }
  }
}

2.快速排序

快速排序（Quick Sort）

快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：

  • 1.从数列中挑出一个元素，称为 “基准”（pivot）；
  • 2.重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
  • 3.递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
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 Quicksort(int arr[], int low, int high) {
	if (low < high) {
		//双指针，一个指向数组起始，一个指向数组末尾
		int i = low;
		int j = high;
		//将数组的第一个元素作为key寻找它的位置
		//key找到它的位置后，以它为分界线，左右两个数组分治
		int key = arr[i];
		while (i < j) {
			//两个指针不相遇，且指针指向的值大于key时，不断左移
			while (i < j && arr[j] >= key)
				j--;
			if (i < j) arr[i] = arr[j];
			//两个指针不相遇，且指针指向的值小于key时，不断右移
			while (i < j && arr[i] <= key)
				i++;
			if (i < j) arr[j] = arr[i];
		}
		//将key放在适合的位置
		arr[i] = key;
		//分治
		Quicksort(arr, low, i - 1);
		Quicksort(arr, i + 1, high);
	}
}

堆排序（Heap Sort）

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

  • 1.将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
  • 2.将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
  • 3.由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-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
// Heapsort.cpp : 定义控制台应用程序的入口点。
//
 
#include "stdafx.h"
#include<iostream>
using namespace std;
void swap(int arr[], int a, int b)		//交换元素；
{
	int temp = arr[a];
	arr[a] = arr[b];
	arr[b] = temp;
}
void adjustHeap(int arr[], int i, int length)		//调整大顶堆（仅是调整过程，建立在大顶堆已构建的基础上）
{
	int temp = arr[i];//先取出当前元素i
	for (int k = i * 2 + 1; k<length; k = k * 2 + 1)//从i结点的左子结点开始，也就是2i+1处开始
	{
		if (k + 1<length&&arr[k]<arr[k + 1])//如果左子结点小于右子结点，k指向右子结点
		{
			k++;
		}
		if (arr[k] >temp)//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
		{
			arr[i] = arr[k];
			i = k;
		}
		else
		{
			break;
		}
	}
	arr[i] = temp;//将temp值放到最终的位置
}
void Heapsort(int arr[], int length)
{
	//1.构建大顶堆
	for (int i = length / 2 - 1; i >= 0; i--)
	{
		//从第一个非叶子结点从下至上，从右至左调整结构
		adjustHeap(arr, i, length);
	}
	for (int j = length - 1; j>0; j--)
	{
		swap(arr, 0, j);//将堆顶元素与末尾元素进行交换
		adjustHeap(arr, 0, j);//重新对堆进行调整
	}
 
}
int main()
{
	int arr[9] = { 9,8,7,6,10,4,3,2,1 };
	Heapsort(arr, 9);
	for (int i = 0; i<9; i++)
		cout << arr[i] << " ";
	cout << endl;
	return 0;
}

归并排序

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

  • 1.把长度为n的输入序列分成两个长度为n/2的子序列；
  • 2.对这两个子序列分别采用归并排序；
  • 3.将两个排序好的子序列合并成一个最终的排序序列。
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
/* 初始版本，升序排序 */
/* 时间复杂度：O(nlbn) 将n个待排序记录归并次数为lbn，一趟归并O(n)
   空间复杂度：O(n) 递归栈最大深度为[lbn] + 1 ，而辅助数组大小为n
   稳定：无论最好还是最坏情况时间复杂度都是O(nlbn)
*/
 
void Merge(int arr[], int n)
{
    int temp[n]; // 用一个额外的数组来进行排序
    int b = 0; // 额外数组的起始位置
    int mid = n / 2; // mid将数组从中间划分，前后两半都有序
    int first = 0, second = mid; // 两个有序序列的起始位置
 	//以下操作类似于将两个数组合并为一个有序数组
    while (first < mid && second < n)
    {
        if (arr[first] <= arr[second]) // 比较两个序列
        	//这步操作相当于把第一个数组的值放到用来排序的数组，接着两个指针后移对下一个值进行操作
            temp[b++] = arr[first++];
        else
            temp[b++] = arr[second++];
    }
 
    while(first < mid)  // 将剩余子序列复制到辅助序列中
            temp[b++] = arr[first++];
    while(second < n)
            temp[b++] = arr[second++];
    for (int i = 0; i < n; ++i) // 辅助序列复制到原序列
        arr[i] = temp[i];
}
 
void MergeSort(int arr[], int n)
{
    if (n <= 1) // 递归出口
        return;
    if (n > 1)
    {
        MergeSort(arr, n / 2); // 对前半部分进行归并排序
        MergeSort(arr + n / 2, n - n / 2); // 对后半部分进行归并排序
        Merge(arr, n); // 归并两部分
    }
}

希尔排序

简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

  • 1.选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
  • 2.按增量序列个数k，对序列进行k 趟排序；
  • 3.每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为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
void shellSort(int a[], int n)  //a -- 待排序的数组, n -- 数组的长度
{
    int i,j,gap;   // gap为步长，每次减为原来的一半。
    for (gap = n / 2; gap > 0; gap /= 2)
    {
        // 共gap个组，对每一组都执行直接插入排序
        for (i = 0 ;i < gap; i++)
        {
            for (j = i + gap; j < n; j += gap) 
            { 
                // 如果a[j] < a[j-gap]，则寻找a[j]位置，并将后面数据的位置都后移。
                if (a[j] < a[j - gap])
                {
                    int tmp = a[j];
                    int k = j - gap;
                    while (k >= 0 && a[k] > tmp)
                    {
                        a[k + gap] = a[k];
                        k -= gap;
                    }
                    a[k + gap] = tmp;
                }
            }
        }
    }
}

《小练习》

1. [NOIP2006 普及组] 明明的随机数

题目描述

明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了 $N$ 个 $1$ 到 $1000$ 之间的随机整数 $(N\leq100)$，对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。

输入格式

输入有两行，第 $1$ 行为 $1$ 个正整数，表示所生成的随机数的个数 $N$。

第 $2$ 行有 $N$ 个用空格隔开的正整数，为所产生的随机数。

输出格式

输出也是两行，第 $1$ 行为 $1$ 个正整数 $M$，表示不相同的随机数的个数。

第 $2$ 行为 $M$ 个用空格隔开的正整数，为从小到大排好序的不相同的随机数。

样例 #1

样例输入 #1

1
2
10
20 40 32 67 40 20 89 300 400 15

样例输出 #1

1
2
8
15 20 32 40 67 89 300 400

提示

NOIP 2006 普及组 第一题

2.宇宙总统

题目描述

地球历公元 6036 年，全宇宙准备竞选一个最贤能的人当总统，共有 $n$ 个非凡拔尖的人竞选总统，现在票数已经统计完毕，请你算出谁能够当上总统。

输入格式

第一行为一个整数 $n$，代表竞选总统的人数。

接下来有 $n$ 行，分别为第一个候选人到第 $n$ 个候选人的票数。

输出格式

共两行，第一行是一个整数 $m$，为当上总统的人的号数。

第二行是当上总统的人的选票。

样例 #1

样例输入 #1

1
2
3
4
5
6
5
98765
12365
87954
1022356
985678

样例输出 #1

1
2
4
1022356

提示

票数可能会很大，可能会到 $100$ 位数字。

$1 \leq n \leq 20$。

3.魔法照片

题目描述

一共有 $n$ 个人（以 $1\sim n$ 编号）向佳佳要照片，而佳佳只能把照片给其中的 $k$ 个人。佳佳按照与他们的关系好坏的程度给每个人赋予了一个初始权值 $W_i$。然后将初始权值从大到小进行排序，每人就有了一个序号 $D_i$（取值同样是 $1\sim n$）。按照这个序号对 $10$ 取模的值将这些人分为 $10$ 类。也就是说定义每个人的类别序号 $C_i$ 的值为 $(D_i-1)\bmod 10 +1$，显然类别序号的取值为 $1 \sim 10$。第 $i$ 类的人将会额外得到 $E_i$ 的权值。你需要做的就是求出加上额外权值以后，最终的权值最大的 $k$ 个人，并输出他们的编号。在排序中，如果两人的 $E_i$ 相同，编号小的优先。

输入格式

第一行输入用空格隔开的两个整数，分别是 $n$ 和 $k$。

第二行给出了 $10$ 个正整数，分别是 $E1\sim E{10}$。

第三行给出了 $n$ 个正整数，第 $i$ 个数表示编号为 $i$ 的人的权值 $W_i$。

输出格式

只需输出一行用空格隔开的 $k$ 个整数，分别表示最终的 $W_i$ 从高到低的人的编号。

样例 #1

样例输入 #1

1
2
3
10 10
1 2 3 4 5 6 7 8 9 10
2 4 6 8 10 12 14 16 18 20

样例输出 #1

1
10 9 8 7 6 5 4 3 2 1

提示

对于 $100\%$ 的数据，$1\leq n\leq 20000$，$1\leq k\leq n$，保证所有数据均在 int 范围之内。

关于

本篇文章作者是SepiaTruck34735。