[数据结构与算法]8.七大排序

七大排序

1.排序的基本概念与分类

①排序的基本概念

假设有n个记录的序列为{r1, r2, …, rn},其对应的关键字分别为{k1, k2, k3, …, kn},需要确定1, 2, …, n的一种排列p1, p2, …, pn,使得其对应的关键字满足，kp1 ≤ kp2 ≤ … ≤ kpn，即使得序列称为一个按关键字有序的序列{rp1, rp2, … rpn}，这样的操作就叫做排序。

如：序列关键字为{2, 3, 5, 1},对其进行升序排列后，得到的结果为{1, 2, 3, 5}。

②排序的稳定性

排序不仅可以针对主关键字排序（一个主关键字对应一条唯一的记录），也可以针对次关键字排序（一条次关键字对应多条记录），因为排序的记录序列中可能出现两个或两个以上的关键字相等的记录，排序结果可能出现不唯一的情况，因此我们给出了稳定与不稳定排序的定义如下：

假设ki = kj(i ≤ i ≤ n， 1 ≤ j ≤ n， i ≠ j),且在排序前的序列中ri领先于rj(i ＜ j)。如果排序后ri仍领先rj，则称为所用的排序方法是稳定的；反之，可能使得排序后的序列中rj领先于ri，则称所用的排序方法是不稳定的。

如：下记录表对分数进行升序排列。

未排序时张三在钱六前面，对于稳定排序后，张三依旧在钱六前面；然而对于不稳定排序，可能出现张三在钱六前面，也可能出现钱六在张三前面。

③内排序与外排序

内排序：在排序整个过程中，待排序的所有记录全部放置在内存中。

外排序：由于排序的记录太多，不能同时放在内存中，整个排序过程需要在内外存之间多次交换数据才能进行。

④影响排序算法的性能的因素

• 时间性能：排序算法的时间开销是衡量其好坏的最重要标志，用时间复杂度O来表示。
• 辅助空间： 辅助存储空间是除了存放待排序所占用的存储空间之外，执行算法所需要的其他存储空间。
• 算法的复杂性： 指的是算法本身的复杂度，而不是时间复杂度。

2.冒泡排序

冒泡排序是一种交换排序，它的基本思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。

每一次冒泡将序列未排序部分的最大值冒泡到未排序部分序列末尾。

如：待排序序列是{9，5，1，8，3}，序列长度为5。

先来看第一次冒泡过程：

黄色为待排序序列，红色代表已经排序完成的部分，每一次冒泡是对上一次冒泡后的待排序序列进行排序。 整个排序过程如下图：

其C++代码如下：

void bubbleSort(vector<int> &nums) {
    //设记录序列长度为n
    //外循环，冒泡次数为n-1次
    for (int i = 0; i < nums.size() - 1; ++i) {
        //内循环，每一次冒泡需要比较n - i次
        for (int j = 1; j < nums.size() - i; ++j) {
            if (nums[j] < nums[j - 1]) {
            swap(nums[j], nums[j - 1]);
            }
        }
    }
}

冒泡排序时间复杂度为：O(n^2)。

冒泡排序空间复杂度为：O(1)。

3.简单选择排序

简单选择排序算法就是通过n - i次关键字间的比较，从n - i + 1个记录中选出关键字最小的记录，并和第i(1 ≤ i ≤ n)个记录交换。

每次从待排序列种选出一个最小值，然后与待排序序列的第一个元素互换，直到全部待排序列数据排完即可。

如：待排序序列为{9，5，1，8，3}，序列长度为5

先来看一次选择过程：

黄色为待排序序列，红色代表已经排序完成的部分，每一次选择是对上一次选择后的待排序序列进行排序。 整个排序过程如下图：

其C++代码如下：

void selectSort(vector<int> &nums) {
    //设记录序列长度为n
    //外循环，选择次数为n-1次
    for (int i = 0; i < nums.size() - 1; ++i) {
        int min = i; //选择待排序序列的第一个元素作为每次选择开始的最小值
        //内循环，每一次选择需要比较n - i - 1次
        for (int j = i + 1; j < nums.size(); ++j) {
            if (nums[j] < nums[min]) {
                min = j;
            }
        } 
        if (min != i) {
            swap(nums[i], nums[min]);
        }
    }
}

直接选择排序时间复杂度为：O(n^2)。 虽然都是O(n ^2)，但简单选择排序性能略优于冒泡排序。

直接选择排序空间复杂度为：O(1)。

4.直接插入排序

直接插入排序的基本操作是将未排序好序列的第一个元素插入到已经排好序的序列中。

如：待排序序列为{9，5，1，8，3}，序列长度为5

先来看一次插入过程，黄色为待排序序列，红色代表已经排序完成的部分，前面4个元素已经排序好了，将最后一个待排元素3插入到排序序列中:

整个排序过程如下：

C++代码如下：

void insertSort(vector<int> &nums) {
    //设记录序列长度为n
    //外循环，插入次数为n - 1次
    for (int i = 0; i < nums.size() - 1; ++i) {
        int end = i;  //end为已排序序列最后一个元素下标
        int temp = nums[i + 1]; //temp用来保存待插入元素
        //内循环，最多循环i次
        while (end >= 0) {
            if (nums[end] > temp) {
                nums[end + 1] = nums[end];
                --end;
            } else {
                break;
            }
        }
        nums[end + 1] = temp;
    }
}

直接插入排序时间复杂度为：O(n^2)。 虽然都是O(n ^2)，但直接插入排序性能优于简单选择排序和冒泡排序。

直接插入排序空间复杂度为：O(1)。

5.希尔排序

直接插入排序在记录序列本身就是基本有序或者记录序列比较短时效率比较高，然而这两个条件比较苛刻，但是没有条件我们可以创造条件。

我们可以把待排序序列分为若干个子序列，此时每个子序列的记录序列就比较短了，对这些子序列分别进行插入排序，当整个序列都基本有序时，对整个序列进行一次直接插入排序，这样效率就提高了。

希尔排序的思想是，先选定一个小于N的整数gap作为第一增量，将所有距离为gap的元素分在同一组，对每一组元素分别进行插入排序，这样就能做到基本有序。然后取比N小的gap重复上述操作，直到gap = 1，相当于对整个序列进行了一次直接插入排序，排序完成。

例如：待排序序列为{9，1，5，8，3，7，4，6}，序列长度为8.

整个排序过程如下：

• 令第一增量gap = 8 / 2 = 4，分成4组子序列，对每组子序列分别进行直接插入排序。

• 第二增量gap = 4 / 2 = 2,分成2组子序列，对每组子序列分别进行直接插入排序。

• 第三增量gap = 2 / 2 = 1,相当于对整个序列进行一次直接插入排序。

• 排序完成

C++代码如下：

void shellSort(vector<int>& nums) {
	int n = nums.size();
	int gap = n;
	while (gap > 1) {
		gap = gap / 2;
		for (int i = 0; i < n - gap; ++i) {
			int end = i;
			int temp = nums[end + gap];
			while (end >= 0) {
				if (nums[end] > temp) {
					nums[end + gap] = nums[end] ;
					end -= gap;
				} else {
					break;
				}
			}
			nums[end + gap] = temp;
		}
	}
}

希尔时间复杂度为：O(n^?)。 终于使得时间复杂度超越了O(n^2)。

直接插入排序空间复杂度为：O(1)。

6.堆排序

6.1大顶堆和小顶堆

堆是具有下列性质的完全二叉树：

• 每个结点的值都大于等于其左右孩子结点的值，称为大顶堆
• 每个结点的值都小于等于其左右孩子的值，称为小顶堆。

如下图的大顶堆和小顶堆

二叉树的编号结点具有如下性质，对于任意编号索引大于0的结点，有：

• 父结点的编号索引为：(k - 1) / 2。
• 左孩子的编号索引为：2 × k + 1。
• 右孩子的编号索引为：2 × k + 2。

堆的定义用上面的性质来描述的话，则有：

• 大根堆：arr[k] > arr[2 × k + 1] && arr[k] > arr[2 × k + 2]
• 小根堆：arr[k] < arr[2 × k + 1] && arr[2 × k + 1] < arr[2 × k + 2]

6.2堆排序算法

堆排序就是利用堆进行排序的方法，升序排序用大顶堆，降序排序用小顶堆。 以升序排序为例，它的基本思想是：

• 将待排序的序列构造成一个大顶堆，此时整个序列的最大值就是堆顶的根结点。
• 将它与堆数组的末尾元素进行交换，此时末尾元素就是最大值。
• 将除了末尾元素的剩余的n - 1个序列重新构造成一个大顶堆，重复上述步骤，便能得到一个有序序列了。

因此，堆排序算法主要要解决两个问题：

1. 如何将无序序列构建成一个堆？
2. 如何在输出堆顶元素后，调整剩余元素为一个新的堆？

①构造堆

构造堆的主要思路:每插入一个结点都要满足新的堆为大顶堆。每次新插入的数据都与父结点进行比较，如果插入的数比父节点大，则与父节点交换，否则一直向上交换，直到小于等于父节点，或者来到了顶堆。

例如：待排序序列为{1，5，9，8，3}，序列长度为5,将其构造成一个大顶堆

整个构造过程如下：

• 插入第一个结点为根节点，天然满足大顶堆要求。

• 插入5，5比父节点1大，则交换两个结点。

• 插入9，9比父节点5大，则交换2个结点。

• 插入结点8，比父结点1小，交换两个结点；接着与其父节点9比较，比父结点9小，维持不变。

• 新插入结点3，比其父结点8小，保持不变。

• 一个大顶堆就构建成功了。

然而这种构造方法需要额外的空间来存放堆，那么我们有什么方法可以直接对给定的数组进行调整成一个堆呢？

②调整一个数组变成一个堆

如：对vector<int> nums {1, 5, 8, 9, 3}进行调整为一个大顶堆

如果从根节点向下调整，选择左右孩子中较大的一个交换，那么根节点得出的结果很可能不是最大的值。如上图，根节点1左右孩子中选择较大的交换，那么根的值变成8，并不是最大值。

因此，只能从倒数第二层开始向上进行调整。 过程如下：

• 最后一个结点的编号为4，其双亲结点编号（4 - 1） / 2 = 1,对1结点进行调整。5的左右孩子较大的值为9，则与9交换。

  

• 编号1的前一个结点是编号0的结点即根节点，拿顶端的数与其左右孩子较大的数进行比较，如果顶端的数大于左右孩子较大的数，则停止；如果小于左右孩子较大的数，则交换。然后继续与下面的孩子进行比较。

③固定堆顶元素并将剩余元素重新调整一个堆

主要思路是：将堆顶与最后一个元素进行交换并固定。将其余数组重新构造成一个大顶堆，即拿顶端的数与其左右孩子较大的数进行比较，如果顶端的数大于左右孩子较大的数，则停止；如果小于左右孩子较大的数，则交换。然后继续与下面的孩子进行比较。

对上述堆进行重排，过程如下：

• 交换堆顶和最后一个元素进行交换固定9，其余部分重新构成大顶堆。3小于其左右孩子较大的8，交换。3与其左孩子1比，大于1，保持不变。

• 交换堆顶和最后一个元素进行交换固定8，其余部分重新构成大顶堆。1小于其左右孩子较大的5，交换。

• 交换堆顶和最后一个元素进行交换固定5，其余部分重新构成大顶堆。1小于其左孩子3，交换。

• 交换堆顶和最后一个元素进行交换固定3，其余部分重新构成大顶堆。

• 固定根节点。

其C++代码如下：

//选定的结点与其左右孩子较大的数进行比较，如果选定的结点大于左右孩子较大的数，则停止；如果小于左右孩子较大的数，则交换。然后继续与下面的孩子进行比较。
void adjust(vector<int> &nums, int i, int len) {
    while (i * 2 + 1 <= len) {
        int leftChild = 2 * i + 1;
        int rightChild = 2 * i + 2;
        int large = 0;
        if (leftChild <= len && nums[leftChild] > nums[i]) {
            large = leftChild;
        } else {
            large = i;
        }
        if (rightChild <= len && nums[rightChild] > nums[large]) {
            large = rightChild;
        }
        if (large != i) {
            swap(nums[i], nums[large]);
            i = large;
        } else {
            break;
        }
    }
}
//从倒数第二层向上建立大顶堆
void buildMaxHeap(vector<int> &nums, int len) {
    for (int i = len / 2; i >= 0; --i) {
        adjust(nums, i, len);
    }
} 
void heapSort(vector<int> &nums) {
    int len = nums.size() - 1;
    buildMaxHeap(nums, len);
    for (int i = len; i >= 1; --i) {
        swap(nums[i], nums[0]);
        len -= 1;
        adjust(nums, 0, len);
    }
}

堆排序时间复杂度为：O(nlogn)。

堆排序空间复杂度为：O(1)。

堆排序是一种不稳定排序。

7.归并排序

如果我们统计全国收入中位数、最大值等，一般中央都要划到各个省，各个省又要划到各个市，各个市又划到各个街道分开统计各自的一小部分数据，然后逐渐合并到中央，就得到了全国的数据。归并排序的思想也是如此。

归并排序的原理是：结社初始序列中含有n个记录，则可以堪称n个有序的子序列，每个子序列的长度为1，然后两两合并，得到n/2个有序的子序列；再两两归并，…，如此重复，直至得到一个长度为n的有序序列为止。

如：序列{16，7，13，10，9，15，3，2}进行归并排序。

C++代码如下：

vector<int> tmp;
void mergeSort(vector<int> &nums, int left, int right) {
    if (left >= right) return;
    int mid = (left + right) / 2;
    mergeSort(nums, left, mid);
    mergeSort(nums, mid + 1, right);
    int i = 1, j = mid + 1;
    int cnt = 0;
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j]) {
            tmp[cnt++] = nums[i++];
        } else {
            tmp[cnt++] = nums[j++];
        }
    }
    while (i <= mid) {
        tmp[cnt++] = nums[i++];
    }
    while (j <= right) {
        tmp[cnt++] = nums[j++];
    }
    for (int i = 0; i < right - 1 + 1; ++i) {
        nums[i + 1] =tmp[i];
    }
}

堆排序时间复杂度为：O(nlogn)。

堆排序空间复杂度为：需要一个临时空间存放归并好的区间的数据。

堆排序是一种稳定排序。

8.快速排序

快速排序是对冒泡排序的优化，其基本思想是：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。

具体来说就是选择一个关键字，然后想办法把它放到一个位置，使得它左边的关键字都比它小，右边的关键字都比它大，这样的关键字我们称为枢轴（pivot）。具体做法如下：

• 选择一个元素的关键字作为key。
• 定义两个指针left指向第一个元素，right指向最后一个元素。
• right向左寻找小于等于pivot的元素，交换left和right的元素。left向右寻找大于等于pivot的元素，交换left和right的元素。重复这个过程直至left = right,此时位置为pos。
• 对 [0, pos - 1]和[pos + 1, end]分别递归调用快速排序算法。

从下面的例子来说明。

例：对数组{50，10，90，30，70，40，80，60，20}进行排序。

过程如下：

• 选取第一个元素50作为pivot，left指向第一个元素，right指向最后一个元素。

• right指向20小于50，调换left和right。

• 接着left向左寻找大于等于50的元素，找到90，交换left和right。

• 接着重复上述过程，right向左寻找小于等于50的元素，找到40，调换left和right。

• left向右寻找大于50的元素，找到70，调换left和right。

• right向左遇到left，此时的位置为pos。

• 接着对[0, pos - 1]和[pos + 1, 7]两个区间分别进行递归上述过程。

• 不断重复上述过程直至排序成功。

C++代码如下：

//一趟排序将序列划分成枢轴pivot左右两部分,并返回枢轴pivot位置
int partition(vector<int>& nums, int left, int right) {
	int pivot = nums[left];
	while (left <= right) {
		while (left < right && nums[right] >= pivot) {
			--right;
		}
		swap(nums[left], nums[right]);
		while (left < right && nums[left] <= pivot) {
			++left;
		}
		swap(nums[left], nums[right]);
        if (left == right) break;
	}
	return left;
}
//快速排序
void quickSort(vector<int>& nums, int left, int right) {
	if (left < right) {
		int pivot = partition(nums, left, right);
		quickSort(nums, left, pivot - 1);
		quickSort(nums, pivot + 1, right);
	}
}

最优情况下，快速排序时间复杂度为O(nlogn)。

然而，在最坏的情况下，待排序的序列是正序或者倒序，每次划分只比上次划分少一个记录的子序列就变成了斜树，效率会大大下降，时间复杂度退化为O(n^2)。

这就需要对快速排序进行改进，我们可以随机取一个关键字作为我们的枢轴pivot。

C++代码如下：

//一趟排序将序列划分成枢轴pivot左右两部分,并返回枢轴pivot位置
int partition(vector<int>& nums, int left, int right) {
	int random = rand() % (right - left + 1) + left;
	int pivot = nums[random];
	while (left <= right) {
		while (left < right && nums[right] >= pivot) {
			--right;
		}
		swap(nums[left], nums[right]);
		while (left < right && nums[left] <= pivot) {
			++left;
		}
		swap(nums[left], nums[right]);
        if (left == right) break;
	}
	return left;
}
//快速排序
void quickSort(vector<int>& nums, int left, int right) {
	if (left < right) {
		int pivot = randPartition(nums, left, right);
		quickSort(nums, left, pivot - 1);
		quickSort(nums, pivot + 1, right);
	}
}

快速排序时间复杂度为：O(nlogn)。

快速排序空间复杂度为：O(1)

快速排序是一种不稳定排序。