[牛客网算法]--排序

排序(一)基础排序算法

冒泡排序

时间复杂度为O(N2)

过程:

  • 循环空间为0到N-1,第一个数和第二个数比较,较大的放在后面,第二个和第三个数比较,较大的放在后面,一直循环到最后,最大的数放在最后面N-1位置。
  • 循环空间为0到N-2,依次比较相邻的数,最大的数放在N-2位置。
  • 循环空间为0到1,最大的数放在1位置。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class BubbleSort {
public:
int* bubbleSort(int* A, int n) {
// write code here
for(int i=n-1;i>=1;i--){
for(int j=0;j<i;j++){
if(A[j]>A[j+1]){
int t = A[j];
A[j]=A[j+1];
A[j+1]=t;
}
}
}
return A;
}
};

选择排序

时间复杂度为O(N2)

过程:

  • 循环空间为0到N-1,选择最小的和0位置交换
  • 循环空间为1到N-1, 选择最小的和1位置交换
  • 循环空间为N-2到N-1,选择最小的和N-2交换
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    class SelectionSort {
    public:
    int* selectionSort(int* A, int n) {
    // write code here
    for(int i=0;i<n-1;i++){
    int min = i;
    for(int j=i+1;j<n;j++){
    if(A[j]<=A[min])min=j;
    }
    int t = A[i];
    A[i]=A[min];
    A[min]=t;
    }
    return A;
    }
    };

插入排序

时间复杂度为O(N2)

过程:

  • 循环空间为0-1,如果位置1上的数小于位置0上的数,交换
  • 循环空间为0-2,如果位置2上的数小于前面位置的数,前面位置的数往后移动
  • 循环空间为0-N-1,如果位置N上的数小于前面的数,前面位置的数往后移动
  • 直到前面的数小于等于当前比较的数,这个数就插入该位置,后面的数往后移
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    class InsertionSort {
    public:
    int* insertionSort(int* A, int n) {
    // write code here
    for(int i=1;i<=n-1;i++){
    int k = A[i];
    int j;
    for(j=i-1;j>=0;j--){
    if(A[j]>=k)A[j+1]=A[j];
    else break;
    }
    A[j+1]=k;
    }
    return A;
    }
    };

归并排序

时间复杂度为O(N*logN)

过程:

  • 数组的每一个数变成长度为1的有序空间,把相邻的组进行合并,得到最大长度为2的有序区间
  • 将长度为2的有序区间进行合并,得到最大长度为4的有序区间
  • 一直进行下去,直到得到只有一个有序区间停止
    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
    class MergeSort {
    public:
    int *mergeSort(int *A, int n) {
    // write code here
    mergeSort1(A,0,n-1);
    return A;
    }

    void Merge(int *A, int low, int mid, int high) {
    int i = low;
    int j = mid + 1;
    int k = 0;
    int *B = new int[high - low + 1];

    while (i <= mid && j <= high) {
    if (A[i] <= A[j]) {
    B[k++] = A[i++];
    } else {
    B[k++] = A[j++];
    }
    }
    while (i <= mid) {
    B[k++] = A[i++];
    }
    while (j <= high) {
    B[k++] = A[j++];
    }
    for (k = 0, i = low; i <= high; i++, k++) {
    A[i] = B[k];
    }
    }

    void mergeSort1(int *A, int low, int high) {
    if (low >= high)return;
    int mid = (low + high) / 2;
    mergeSort1(A, low, mid);
    mergeSort1(A, mid + 1, high);
    Merge(A, low, mid, high);
    }
    };

快速排序

时间复杂度为O(N*logN)

过程:

  • 随机的在数组中选择一个数,将小于等于该数的放在这个数的前面,大于该数的放在该数的后面
  • 左边选出的数和右边选出的数又随机选择一个数,依次递归调用上述过程

完整划分过程(时间复杂度为O(N)):

  • 将划分值和最后一个元素交换,设定划分区间为-1
  • 依次遍历,如果当前元素大于划分值,比较下一个元素
  • 如果当前元素小于划分值,将该元素和划分区间+1的位置元素交换,然后将划分区间值加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
    class QuickSort {
    public:
    int *quickSort(int *A, int n) {
    // write code here
    qSort(A,0,n-1);
    return A;
    }

    int partion(int *A, int low, int high) {
    int div = low - 1;
    int t;
    for (int i = low; i < high; i++) {
    if (A[i] <= A[high]) {
    t = A[div + 1];
    A[div + 1] = A[i];
    A[i] = t;
    div++;
    }
    }
    t = A[div + 1];
    A[div + 1] = A[high];
    A[high] = t;
    return div+1;
    }

    void qSort(int *A, int low, int high){
    if(low>=high)return;
    int p=partion(A,low,high);
    qSort(A,low,p-1);
    qSort(A,p+1,high);
    }
    };

堆排序

时间复杂度为O(N*logN)

过程:

  • 将数组中的N个数建立成为大小为N的大根堆
  • 将堆顶的值和堆最后一个值交换,选出最大值,将此值剔除该堆,放在数组位置N
  • 将大小为N-1的堆进行大根堆的调整,将N-1数中的最大值放在堆顶的位置,将堆顶的位置和堆最后一个元素交换,将此值剔除该堆,放在数组位置N-1
  • 循环直到剩下最后一个元素

希尔排序

时间复杂度为O(N*logN)

过程:

  • 设定步长为3
  • 比较位置3的数和位置3-3的数,如果小,则交换,再比较0-3<0,下一步
  • 比较位置4的数和位置4-3的数,如果小,则交换,再比较1-3<0,下一步
  • 比较位置5的数和位置5-3的数,如果小,则交换,再比较2-3<0,下一步
  • 比较位置5的数和位置6-3的数,如果小,则交换,再比较3-3=0,比较6-3和位置6-3-3的值,如果小,则交换,依次进行上述比较
  • 设定步长为2,过程类似
  • 设定步长为1,过程类似,结束排序
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    class ShellSort {
    public:
    int *shellSort(int *A, int n) {
    // write code here
    int gap = n / 2;
    while (gap > 0) {
    for (int i = gap; i < n; i++) {
    for (int j = i - gap; j >= 0; j -= gap) {
    if (A[j] > A[j + gap]) {
    int t = A[j];
    A[j] = A[j + gap];
    A[j + gap] = t;
    }
    }
    }
    gap = gap / 2;
    }
    return A;
    }
    };

排序(二)计数排序算法

计数排序和基数排序

不是基于比较的排序,思想来源于桶排序,有计数排序和基数排序。

计数排序

原理
计数排序非常基础,他的主要目的是对整数排序并且会比普通的排序算法性能更好。例如,输入{1, 3, 5, 2, 1, 4}给计数排序,会输出{1, 1, 2, 3, 4, 5}。这个算法由以下步骤组成:

  • 初始化一个计数数组,大小是输入数组中的最大的数。
  • 遍历输入数组,遇到一个数就在计数数组对应的位置上加一。例如:遇到5,就将计数数组第五个位置的数加一。
  • 把计数数组直接覆盖到输出数组(节约空间)。

例子:
输入{3, 4, 3, 2, 1},最大是4,数组长度是5。
建立计数数组{0, 0, 0, 0}。
遍历输入数组:
{3, 4, 3, 2, 1} -> {0, 0, 1, 0}
{3, 4, 3, 2, 1} -> {0, 0, 1, 1}
{3, 4, 3, 2, 1} -> {0, 0, 2, 1}
{3, 4, 3, 2, 1} -> {0, 1, 2, 1}
{3, 4, 3, 2, 1} -> {1, 1, 2, 1}

计数数组现在是{1, 1, 2, 1},我们现在把它写回到输入数组里:
{0, 1, 2, 1} -> {1, 4, 3, 2, 1}
{0, 0, 2, 1} -> {1, 2, 3, 2, 1}
{0, 0, 1, 1} -> {1, 2, 3, 2, 1}
{0, 0, 0, 1} -> {1, 2, 3, 3, 1}
{0, 0, 0, 0} -> {1, 2, 3, 3, 4}

这样就排好序了。

  • 时间:O(n + k),n是输入数组长度,k是最大的数的大小。
  • 空间:O(n + k),n是输入数组长度,k是最大的数的大小。

代码:

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
class CountingSort {
public:
int *countingSort(int *A, int n) {
// write code here
int i, j, num = 0;
int max = 0, min = 0;
for (int i = 1; i < n; i++) {
if (A[i] > A[max])max = i;
if (A[i] < A[min])min = i;
}
int countmax = A[max];
int countmin = A[min];
int countarray[countmax - countmin + 1];
for (i = 0; i < countmax - countmin + 1; i++) {
countarray[i]=0;

}
for (i = 0; i < n; i++) {
countarray[A[i] - countmin]++;
}
for (i = 0; i < countmax - countmin + 1; i++) {
if (countarray[i] > 0) {
for (j = 0; j < countarray[i]; j++) {
A[num++] = i + countmin;
}
}
}
return A;
}
};

排序(三)习题

小范围排序

题目
已知一个几乎有序的数组,几乎有序是指,如果把数组排好序,每个元素的移动距离不超过k,并且k相对于数组长度来说很小,用什么排序发比较好?

  • 时间复杂度为o(n)的排序算法基数排序和基数排序,不知道数组的范围,因此不做考虑。
  • 时间复杂度为o(n2)的排序算法冒泡排序和选择排序,与原始数组无关;插入排序与原始数据有关,对于本题,插入排序的时间复杂度为o(n*k);
  • 时间复杂度为o(n*logn)的排序算法,快速排序,归并排序与原始无关。
  • 解决方法为改进后的堆排序。

过程

Alt text

数组排序完毕,每得到一个数,代价为o(logk),总共有n个数,时间复杂度为o(n*logk)。

重复值判断

题目
判断数组中是否有重复值,必须保证额外空间复杂度为o(1)。

  • 如果没有空间限制,可以使用哈希表来做,统计是否有重复值。
  • 先排序,然后遍历一遍之后看是否有相同的值

考虑经典排序算法,空间复杂度限制。

Alt text

代码

使用hash表方法代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Checker {
public:
bool checkDuplicate(vector<int> a, int n) {
// write code here
if(n<2) return false;
auto ret = std::minmax_element(a.begin(),a.end());
int min = *ret.first;
int max = *ret.second;
vector<size_t> map(max-min+1,0);
for(auto x:a){
if(++map[x-min]>1)return true;
}
return false;
}
};

使用堆排序方法代码如下

堆排序为大部分为递归实现,因此需要改为非递归版本的堆排序。

有序数组合并

题目
把两个有序数组合并为一个数组,第一个数组的空间正好可以容纳两个数组的元素。
数组A:2 4 6_ _ _
数组B:1 3 5
过程

  • 从后向前覆盖,比较6和5,将6放入最后一个位置。
  • 再比较4和5,将5放入6之前。
  • 依次比较,直到数组B全部复制到数组A中。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Merge {
public:
int* mergeAB(int* A, int* B, int n, int m) {
// write code here
int k = m + n-1;
int i = n-1;
int j = m-1;
while(i>=0&&j>=0){
if(A[i]>=B[j]){
A[k--]=A[i--];
}
else{
A[k--]=B[j--];
}

}
while(j>=0){
A[k--]=B[j--];
}
return A;
}
};

三色排序/荷兰国旗

题目
题目有一个只由0,1,2三种元素构成的整数数组,请使用交换、原地排序而不是使用计数进行排序。
给定一个只含0,1,2的整数数组A及它的大小,请返回排序后的数组。保证数组大小小于等于500。

输入:[0,1,1,0,2,2],6
返回:[0,0,1,1,2,2]

过程

  • 设置一个0区间,指向位置-1;设置一个2区间指向位置n;
  • 从0位置开始遍历,如果遇到1,则跳到下一位置
  • 如果遇到0,则将0和0区间的下一位置的数交换,跳到下一位置;
  • 如果遇到2,则将2和2区间的前一位置的数交换,因为交换的数没有被遍历过,所以从当前位置开始判断;
  • 直到遍历位置和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
class ThreeColor {
public:
vector<int> sortThreeColor(vector<int> A, int n) {
// write code here
int begin = -1;
int end = n;
int t;
for(int i=0;i<end;i++){
if(A[i]==0){
begin++;
t = A[begin];
A[begin] = A[i];
A[i] = t;

}
if(A[i]==2){
end--;
t = A[end];
A[end] = A[i];
A[i] = t;
i--;
}
}
return A;
}
};

有序矩阵查找问题

题目
现在有一个行和列都排好序的矩阵,请设计一个高效算法,快速查找矩阵中是否含有值x。
给定一个int矩阵mat,同时给定矩阵大小nxm及待查找的数x,请返回一个bool值,代表矩阵中是否存在x。所有矩阵中数字及x均为int范围内整数。保证n和m均小于等于1000。

输入:[[1,2,3],[4,5,6],[7,8,9]],3,3,10
返回:false

过程

  • 从矩阵的右上角开始查找,即位置[0][m-1],col=0,row=m-1;
  • 当遍历的数大于需要查找的数的时候,这个数列的下方所有的数都大于需要查找的数,此时应该row–;
  • 当遍历的数小于需要查找的数的时候,这个数行的左边所有的数都小于需要查找的数,此时应该col++;
  • 如果找到此数,则返回true;如果没有找到,则返回false;

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Finder {
public:
bool findX(vector<vector<int> > mat, int n, int m, int x) {
// write code here
if(m <= 0 || n <= 0){
return false;
}
int col=0,row=m-1;
while(col<n&&row>=0){
if(mat[col][row]>x)row--;
else if(mat[col][row]<x)col++;
else return true;
}
return false;
}
};

最短子数组

题目
对于一个数组,请设计一个高效算法计算需要排序的最短子数组的长度。
给定一个int数组A和数组的大小n,请返回一个二元组,代表所求序列的长度。(原序列位置从0开始标号,若原序列有序,返回0)。保证A中元素均为正整数。

输入:[1,4,6,5,9,10],6
返回:2

过程

  • 从左向右遍历,选择当前遍历阶段的最大值,如果遇到比最大值小的,记录下来为maxindex;
  • 从右向左遍历,选择当前遍历阶段的最小值,如果遇到比最小值大的,记录下来为minindex;
  • 如果maxindex-minindex<0,返回0,否则返回maxindex-minindex;

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Subsequence {
public:
int shortestSubsequence(vector<int> A, int n) {
// write code here
int maxindex = 0;
int minindex = n-1;
int max=A[0];
int min=A[n-1];
for(int i =0;i<n;i++){
if(max<=A[i]){
max=A[i];
}else maxindex = i;
}
for(int j = n-1;j>=0;j--){
if(min>=A[j]){
min = A[j];
}else minindex = j;
}
return maxindex>minindex?maxindex-minindex+1:0;
}
};

相邻两数最大差值

题目
有一个整形数组A,请设计一个复杂度为O(n)的算法,算出排序后相邻两数的最大差值。
给定一个int数组A和A的大小n,请返回最大的差值。保证数组元素多于1个。

输入:[1,2,5,4,6],5
返回:2

过程

  • 求出数组的最大值valueMax,最小值valueMin;
  • 初始化设定两个桶bocketMax,bocketMin;初始化为INT_MIN和INT_MAX;
  • 确定桶的长度len=valueMax-valueMin;如果长度小于1,则返回0;
  • 将数组中的每一个元素装到桶中,桶序号index=(A[i]-valueMin)/len*(n-1);
  • 将桶中的最大元素保存在bocketMax,最小元素保存在bocketMin;
  • 遍历数组,如果桶为空,则跳过,如果桶不为空,则用当前桶的最小值减去前一个不为空的pre桶的最大值,得到最大区间,将pre桶移动到当前桶位置,继续遍历,区最大区间的最大值即为所求。

其他方法
先排序再依次求差值

  • 把vector中的元素依次遍历,保存到set中,实现排序;
  • 遍历set,比较相邻的两个元素,得到区间,求区间的最大值。

代码

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
class Gap {
public:
int maxGap(vector<int> A, int n) {
// write code here
int valueMax = A[0], valueMin = A[0];
for(int i=0; i<n; i++){
if(A[i]>valueMax)valueMax = A[i];
if(A[i]<valueMin)valueMin = A[i];
}
vector<int> bocketMax(n, INT_MIN);
vector<int> bocketMin(n, INT_MAX);
int len = valueMax - valueMin;
if(len<1)return 0;
for(int i=0;i<n;i++){
int index = (double)(A[i]-valueMin)/len*(n-1);
bocketMax[index] = max(A[i], bocketMax[index]);
bocketMin[index] = min(A[i], bocketMin[index]);
}
int ret=0, pre = bocketMax[0];
for(int i=1;i<n;i++){
if(bocketMin[i]!=INT_MAX){
ret = max(ret, bocketMin[i]-pre);
pre = bocketMax[i];
}
}
return ret;
}
};

如果文章对您有帮助,请随意打赏