PTA刷题总结-Part3.3 排序专题
2020-04-05 本文已影响0人
苏wisdom
本章节涵盖了冒泡排序O(n^2) 、选择排序O(n^2) 、插入排序O(n^2)、快速排序O(nlogn)和归并排序O(nlogn)的内容。
其中工程上用得最多的是插入排序和快速排序。而在写算法题的时候简单排序可以考虑直接使用库函数sort(首元素地址，尾元素地址的下一个地址，比较函数)，其中最后一个参数“比较函数”非必填。
比如针对int a[] = {3,2,1,4}, 想要升序排序下标[0,2]这三个元素，那么需要调用sort(a, a+3)
#include <algorithm>
#include <vector>
#include <stdio.h>
using namespace std;
vector<int> Arr;
bool cmp(int a, int b){
return a>b;
}
int main(){
Arr.push_back(3);
Arr.push_back(1);
Arr.push_back(2);
sort(Arr.begin(), Arr.end());
for (int i=0; i<Arr.size();i++){
printf("%d ", Arr[i]);
}
printf("\n");
sort(Arr.begin(), Arr.end(),cmp);
for (int i=0; i<Arr.size();i++){
printf("%d ", Arr[i]);
}
printf("\n");
int a[8] = {2,4,5,1,3,9,4,-1};
sort(a, a+7);
for (int i=0; i<8;i++){
printf("%d ", a[i]);
}
}
输出结果依次是
1 2 3
3 2 1
1 2 3 4 4 5 9 -1
1 冒泡排序O(n^2)，稳定
当题目告诉你n的规模超过1000的话，就不能用了。
道理很简单，针对递增排序来说，对数组一共会做n-1趟扫描（i=1;i<=n-1;i++），每次扫描的时候，比较的都是相邻两个数的大小（a[j] > a[j+1]），然后做交换。每趟结束的时候，本趟扫描中的最大值会像气泡一样排到了末尾位置。每趟能够扫描到的数是(j=0;j<n-i;j++)。
- 稳定
- 做交换的次数 = 逆序对数
- 最好O(N)
- 平均O(n^2)
- 空间O(1)
- 内部排序，原地排序
题目：7-73 比较大小 (10分)
#include <stdio.h>
void swap(int *a, int *b){
int temp = *a;
*a = *b;
*b = temp;
}
int main() {
int num[3] = {0};
for (int i=0;i<3;i++){
scanf("%d", &num[i]);
}
for (int i=1;i<=2;i++){
for (int j=0;j<3-i;j++){
if (num[j] > num[j+1]){ // 相等的时候不做交换，所以稳定
swap(&num[j], &num[j+1]);
}
}
}
printf("%d", num[0]);
for (int i=1;i<3;i++){
printf("->%d", num[i]);
}
return 0;
}
如果扫描一趟就发现已经是递增序列了，就不继续扫描了
#include <stdio.h>
void sort ( int a[], int len );
int main(void)
{
int n;
scanf("%d", &n);
int a[n];
for ( int i=0; i<n; i++ ) {
scanf("%d", &a[i]);
}
sort(a, n);
for ( int i=0; i<n; i++ ) {
printf("%d\n", a[i]);
}
}
/* 请在这里填写答案 */
void sort ( int a[], int len ){
int is_sort = 1;
for (int i = len-1;i>0;i--){
is_sort = 1;
for (int j = 0;j<i;j++){
if (a[j] > a[j+1]){
is_sort = 0;
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
if (is_sort) {
break;
}
}
}
2 选择排序 O(n^2)
首先在未排序序列中找到最小元素，存放到排序序列的起始位置。
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
重复第二步，直到所有元素均排序完毕。
同样是O(n^2)的算法复杂度，同样无法处理n的规模超过1000的无序数据。但是冒泡排序针对已经排序好的序列，有O(n)复杂度的优势。
- 不稳定
- 无论什么情况下，都要比较
N*(N-1)/2次 - 最好O(n^2)
- 平均O(n^2)
- 空间O(1)
- 内部排序，原地排序
#include <stdio.h>
void sort ( int a[], int len );
int main(void)
{
int n;
scanf("%d", &n);
int a[n];
for ( int i=0; i<n; i++ ) {
scanf("%d", &a[i]);
}
sort(a, n);
for ( int i=0; i<n; i++ ) {
printf("%d\n", a[i]);
}
}
/* 请在这里填写答案 */
void sort ( int a[], int len ){
for (int i=0;i<len;i++){
int min = i;
for (int j = i+1;j<len;j++){
// 找到无序数组中的最小值
if (a[j] < a[min]){
min = j;
}
}
if (min != i){
int temp = a[i];
a[i] = a[min];
a[min] = temp;
}
}
}
3 直接插入排序 O(n^2)
插入排序也可以引入二分查找进行优化，或者使用每次交换相隔一定元素的希尔排序。但是这里说的是普通的直接插入排序，或者叫简单插入排序。
插入排序假定左侧都是有序的，比如左侧都是升序[0,2,4,5]， 右侧是等待排序的序列，比如[1,7], 那么1就会从数字5开始，逐一向左比较，发现数字比1大，就发生交换（右移动），一直到与数字0比较发现小于1为止，然后把1放到0后面的位置。这个过程就像打扑克牌时的摸牌一样。
简单插入排序效率不高的主要原因是每次只移动相邻的两个元素，这样只能消去一对错位的元素。希尔排序的改进方案是，每次交换相隔一定距离的元素，比如先相隔5，再相隔3，最后相隔1即使用简单插入排序，到最后相隔1的时候，前面的步骤已经交换了很多逆序对。希尔排序是不稳定的，时间复杂度的计算也很复杂。
针对已经排好序的大规模数据，插入排序的表现也是比选择排序要好，接近O(N)，而且我们使用不交换数据直接赋值的方式进行数据的插入，这也比冒泡排序一个个相邻元素都交换有优势。所以冒泡和选择一般停留在理论上，工程上插入排序是用得更多的。
- 稳定
- 做交换的次数 = 逆序对数
- 最好O(N) 已经有序
- 平均O(N^2)
- 空间O(1)
- 内部排序，原地排序
#include <stdio.h>
void sort ( int a[], int len );
int main(void)
{
int n;
scanf("%d", &n);
int a[n];
for ( int i=0; i<n; i++ ) {
scanf("%d", &a[i]);
}
sort(a, n);
for ( int i=0; i<n; i++ ) {
printf("%d\n", a[i]);
}
}
void sort ( int a[], int len ){
for (int i=1;i<len;i++){
int value=a[i];
int j=i;
while (j>0 && a[j-1] > value){
a[j] = a[j-1];
j--;
}
a[j] = value;
}
}
4 快速排序 O(NlogN)，不稳定
注意对于有序数组，使用快排仍然是O(n^2)时间复杂度，也就是说对于n规模大于1000且已知测试点序列可能有序的情况下，就不要使用快排了
https://www.lintcode.com/problem/sort-integers-ii/description
public class Solution {
/**
* @param A: an integer array
* @return: nothing
*/
public void sortIntegers2(int[] A) {
if (A == null || A.length == 0) {
return;
}
quickSort(A, 0, A.length - 1);
}
private void quickSort(int[] A, int start, int end) {
// 已经排好序了
if (start >= end) {
return;
}
int left = start, right = end;
// 获取中间的pivot，是数组值，不是下标
int pivot = A[(start + (end - start) / 2)];
// 所有都是left <= right，保证扫描结束两根指针不重叠，而是right在左，left在右。可能相邻，也可能相隔一个数
while (left <= right) {
// 数组中的值使用A[left] < pivot，不使用相等，保证相等的数均分
while(left <= right && A[left] < pivot) {
left++;
}
while(left <= right && A[right] > pivot) {
right--;
}
if (left <= right) {
int temp = A[left];
A[left] = A[right];
A[right] = temp;
left++;
right--;
}
}
// 最后right会在left左边
quickSort(A, start, right);
quickSort(A, left, end);
}
}
当序列中的元素接近有序时，这种选择pivot的方法时时间复杂度会退化成O(n^2)。
找到第K大的数/中位数
https://www.lintcode.com/problem/kth-largest-element/description
public class Solution {
/**
* @param n: An integer
* @param nums: An array
* @return: the Kth largest element
*/
public int kthLargestElement(int n, int[] nums) {
if (nums == null || nums.length == 0) {
return -1;
}
return findKthLargest(nums, 0, nums.length - 1, n);
}
private int findKthLargest(int[] nums, int start, int end, int k) {
if (start >= end) {
return nums[start];
}
int left = start, right = end;
int pivot = nums[(start + (end - start) / 2)];
while (left <= right) {
while (left <= right && nums[left] > pivot) {
left++;
}
while (left <= right && nums[right] < pivot) {
right--;
}
if (left <= right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left++;
right--;
}
}
if (start + k - 1 <= right) {
return findKthLargest(nums, start, right, k);
}
if (start + k - 1 >= left) {
return findKthLargest(nums, left, end, k - (left - start));
}
return nums[right+1];
}
}
5 归并排序 O(NlogN)，稳定
对于序列[1,2,3,1,4] 5个数
- 第一趟merge下标0~1 得到[1,2]
- 第二趟merge下标0~2 得到[1,2,3]
- 第三趟merge下标3~4 得到[1,4]
- 第四趟merge下标0~4 得到[1,1,2,3,4]
归并排序需要开辟一个临时数组，所以这个数组不能定义在方法中，内存不够。
想象2G的内存，排序2G的数据，如果使用归并排序的话，只有1G的内存可以用。归并排序一般不用于内部排序，是外部排序的有用工具。
#include <stdio.h>
void sort ( int a[], int len );
int main(void)
{
int n;
scanf("%d", &n);
int a[n];
for ( int i=0; i<n; i++ ) {
scanf("%d", &a[i]);
}
sort(a, n);
for ( int i=0; i<n; i++ ) {
printf("%d\n", a[i]);
}
}
int temp[1000000];
void mergeSort(int a[],int left,int right);
void merge(int a[],int l1,int r1,int l2,int r2); // [l1,r1] 和 [l2,r2]
void sort ( int a[], int len ){
mergeSort(a,0,len-1);
}
void mergeSort(int a[],int left,int right){
if (left<right){
int mid = (left+right) >>1;
mergeSort(a,left,mid);
mergeSort(a,mid+1,right);
merge(a,left,mid,mid+1,right);
}
}
void merge(int a[],int l1,int r1,int l2,int r2){
int i=l1,j=l2;
int index = 0;
while (i<=r1 && j<= r2){
if (a[i] <= a[j]){
temp[index++] = a[i++];
} else {
temp[index++] = a[j++];
}
}
// 到此处时，要么i已经等于r1, 要么j已经到达r2
while (i<=r1){
temp[index++] = a[i++];
}
while (j<=r2){
temp[index++] = a[j++];
}
for (i = 0;i<index;i++){
a[l1+i] = temp[i];
}
}
public class Solution {
/**
* @param A: an integer array
* @return: nothing
*/
public void sortIntegers2(int[] A) {
if (A == null || A.length == 0) {
return;
}
int temp[] = new int[A.length];
mergeSort(A, 0, A.length - 1, temp);
}
private void mergeSort(int[] A, int left, int right, int[] temp){
if (left < right) {
int mid = left + (right - left) / 2;
mergeSort(A, left, mid, temp);
mergeSort(A, mid+1, right, temp);
merge(A, left, mid, mid + 1, right, temp);
}
}
private void merge(int[] A, int lleft, int lright, int rleft, int rright, int[] temp){
int i = lleft, j = rleft;
int index = lleft;
while (i <= lright && j <= rright) {
if (A[i] < A[j]) {
temp[index++] = A[i++];
}else {
temp[index++] = A[j++];
}
}
while(i <= lright) {
temp[index++] = A[i++];
}
while(j <= rright) {
temp[index++] = A[j++];
}
for (int k = lleft; k<= rright; k++) {
A[k] = temp[k];
}
}
}
6 堆排序，O(NlogN)，不稳定
原地排序方法：
对于一个N个元素的无序数组（下标从0~N-1），首先建立大顶堆
- 将堆顶元素和最后一个元素交换，即堆顶元素换到了N-1下标
- 对剩下的0~N-2元素重新生成一个大顶堆
- 将当前最大值和第N-2下标元素交换
- 继续反复，知道堆中只剩1个元素，即可停止
