云曦

Choice is more important than effort

0%

排序算法

发表于 更新于 分类于
本文字数： 6.5k 阅读时长 ≈ 6 分钟

算法分类

1、排序

  • 比较类排序

2、复杂度

相关概念

  • 稳定：如果 a 本来在 b 前面，而a = b ，排序之后 a 仍然在 b 的前面
  • 不稳定：如果 a 本来 在b的前面，而 a = b ，排序之后 a 可能在 b 的后面
  • 时间复杂度：对排序数据的总的操作数，反映当 n 变化时，操作次数呈什么变化
  • 空间复杂度： 指算法计算机内执行时所需存空间的度量，也是数据规模 n 的函数

几种常见排序(已学)

1、冒泡排序(Bubble Sort)

~~注：重复地走访序列，一次比较两个元素，如果顺序错误就交换过来，重复地进行直到没有再需要交换，也就说该数列排序完成———->这个算法的名字是因为越小的元素会经由交换慢慢“浮”到顶端

动图展示

aoKJdf.gif

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function bubbleSort(arr) {
    var len = arr.length;
    for (var i = 0; i < len - 1; i++) {
        for (var j = 0; j < len - 1 - i; j++) {  //每次循环最大的元素都被放到最后，就不用管了
            if (arr[j] > arr[j+1]) {        // 相邻元素两两对比
                var temp = arr[j+1];        // 元素交换
                arr[j+1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    return arr;
}

课上讲的模板类写法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
template<class T>
void mySwap(T &x,T &y)
{
	T temp = x;
	x = y;
	y = temp;
}

template<class T>
void bubbldeSort(T a[],int n)
{
	int i= n-1 ;
	while(i>0){
	int lastExchange = 0;//每次都值为 0 ，如果下面的 if语句 不成立，退出循环，说明排序完成
        //(a[j]<a[j+1])都成立
	for(int j=0;j<i;j++)
	  if(a[j+1]<a[j])
	  {
	  mySwap(a[j],a[j+1]);
	  lastExchange = j;  //第一次循环这个 j = n-1，a[j+1]包括后面的数就不用管了
	  }
	  i = lastExchange;
	}
}

2、选择排序(Selection Sort)

~~注：首先在未排序序列中找到最小(大)的元素，存放到排序序列的起始位置，然后再从剩余未排序序列元素中继续寻找最小元素，然后放到已排序序列的末尾。以此类推，直到排序完毕。

动图

aoKYo8.gif](https://imgchr.com/i/aItpqJ)

代码实现;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function selectionSort(arr) {
    var len = arr.length;
    var minIndex, temp;
    for (var i = 0; i < len - 1; i++) {
        minIndex = i; //记录未排序的第一个数，方便后面最小的数与其交换
        for (var j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {     // 寻找最小的数
                minIndex = j;                 // 将最小数的索引保存
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp; //将 i 和最小的数交换 ，然后 i 往后移一位，前面是已经排好的序列
    } 
    return arr;
}

3、插入排序

~注：描述—->

  • 第一个元素已经排序
  • 取出下一个元素，在已经排序的元素序列中从后往前扫描
  • 如果该元素(已排序)大于新元素，将该元素移至下一个位置
  • 重复3，直到找到已排序的元素小于或等于新元素的位置

aoKNFS.gif

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function insertionSort(arr) {
    var len = arr.length;
    var preIndex, current;
    for (var i = 1; i < len; i++) {
        preIndex = i -1; 
        current = arr[i];  //前面的数都是已经排好序的 
        while (preIndex >= 0 &&  arr[preIndex] > current) { //后面的数比前面的大就循环，如果小于或等于就停止循环，进行插入
            arr[preIndex + 1] = arr[preIndex]; //往后挪位置
            preIndex--;
        }
        arr[preIndex+1] = current;  //上面arr[preIndex]往后移了，此时arr[preIndex]为无用值，又减了一，所以要加1；
    }
    return arr;
}
//注释1：从下标为1的元素开始遍历，记作temp-->然后从temp向前遍历将元素往后挪位，直到不满足条件插入此元素

c++模板类写法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
template<class T>
void insertionSort(T a[],int n)
{
	int i,j;
	T temp;
	for(int i=1;i<n;i++)
	{
 	int j=i;
 	T temp = a[i];
	while(j>0 && temp<a[j-1])
	{
		a[j]=a[j-1]; //这里j值并没有改变，下面减去一才是要填充的位置
		j--;
	}
	a[j]=temp; //a[j-1]被移动到后面的序列去了， j-1是无用数据
	}
}
3 2 5 4 9 8 7 temp = 2
2 3 5 4 9 8 7 temp = 5
2 3 4 5 9 8 7 temp = 5
    //注释2：从下标为1开始循环(因为要j-1不能越界)，如果前面的元素比temp(循环选定元素)大，说明要后退一位，以便留一个位置给temp，就这样一直后移直到找到一个数 < temp

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
#include<bits/stdc++.h>
using namespace std;

void countSort(vector<int>& array){
   int max = array[0];
   for(int i=1;i<array.size();i++){// 找出最大值
       if(array[i]>max){
           max = array[i];
       }
   }
   vector<int> countArray(max+1); // 容量为max+1 
    for(int i=0;i<array.size();i++){
        countArray[array[i]]++;
    }

    int index = 0;// countArray下标代表数字，对应的元素值表示
    //出现的次数
    ================================
    for(int i=0;i<countArray.size();i++){
        for(int j=0;j<countArray[i];j++){
            array[index++] = i;
            // 直接修改原数组(参数)
            ================================
        }
    }
}

int main(){
    vector<int> a={4,4,6,5,3,2,8,1,7,5,6,0,10};
    countSort(a);
   for(vector<int>:: iterator it = a.begin();it!=a.end();it++ ){
       cout<<*it<<endl;
   }

    return 0;
}

5、快速排序

  • 基准元素
  • 两边向中间循环查找

双边循环

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
#include <iostream>
#include <vector>
#define N 10
using namespace std;
void sawp(int &a,int &b)// 交换两个数
{
    int temp;
    temp = a;
    a = b;
    b = temp;
}
void quickSort(int left,int right,vector<int> & a)
{
    if(left >= right)
    return;

    int i,j,base;
    i = left, j =right;
    base = a[left];// 基准元素
    while(i < j)
    {
        while(a[j]>=base && i < j) //i <j 基本条件
        j--;

        while(a[i]<=base && i < j)
        i++;

        if(i < j) // 有可能此时i==j
        swap(a[i],a[j]); //交换左边和右边的值，一个大于基准值，一个小于基准值

    }
    a[left] = a[i];
    a[i] = base;
    quickSort(left,i-1,a);//对剩余的部分进行快速排序
    quickSort(i+1,right,a);//
}

y总模板

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
#include <iostream>

using namespace std;

const int N = 1000010;

int q[N];

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int i = l - 1, j = r + 1, x = q[l + r >> 1];
 
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }

    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

int main()
{
    int n;
    scanf("%d", &n);

    for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);

    quick_sort(q, 0, n - 1);

    for (int i = 0; i < n; i ++ ) printf("%d ", q[i]);

    return 0;
}

单边循环>

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

#include <iostream>
#include <vector>
#define N 10
using namespace std;
void sawp(int &a, int &b) { // 交换两个数
	int temp;
	temp = a;
	a = b;
	b = temp;
}

void quickSort(vector<int> &a, int L, int R) {

    if(L>=R){
        return; // 递归结束条件
    }
	// L,R表示起始和终点下标
	int p = a[L];
	int mark = L;
    
	for (int i = L + 1; i <= R; i++) {
        
		if (a[i] < p) {
            cout<<p<<"  >  "<<a[i]<<endl;
            cout<<"mark值为"<<mark<<endl;
			mark++;
            cout<<"mark值为"<<mark<<endl;
			swap(a[mark], a[i]); //此时mark表示a[mark]>p,把小的
			// 提到前面来
          
   
		}
	}
    
	swap(a[mark], a[L]);
    
	quickSort(a, L, mark - 1);
	quickSort(a, mark + 1, R);
}

int main() {
	vector<int> a = {4,7,3,5,6,2,8,1};
	quickSort(a, 0, a.size() - 1);
	for (int i = 0; i < a.size(); i++) {
		cout << a[i] << " ";
	}
	return 0;
}

6.归并排序

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
// 归并排序
#include<iostream>
using namespace std;
const int N = 100010;
int a[N]; // 数据数组和排序数组

void merge(int A[], int L1, int R1, int L2, int R2) // 表示两个数组左右端点下标
{
    int i = L1, j = L2;
    int index = 0;
    int temp[N];
    while(i <= R1 && j <= R2) // 循环完后可能有其中一个数组还没选完
    {
        if(a[i] <= a[j])    temp[index++] = a[i++];

        if(a[i] >= a[j])    temp[index++] = a[j++]; 
    }
    // 把剩下的数填进数组后面
    while(i <= R1)  temp[index++] = a[i++];
    while(j <= R2)  temp[index++] = a[j++];

    for(int k = 0;k < index;k++)
    a[L1 + k] = temp[k]; // 把temp数组赋给原数组对应的位置
}
void mergesort(int A[], int left,int right) // 左端点下标和右端点下标
{
    if(left < right)
    {
    int mid = (left + right) / 2;
    mergesort(a, left, mid);
    mergesort(a, mid + 1, right);
    merge(A, left, mid, mid + 1, right); // 合并两个序列并排序
    }
}


int main()
{
    int n;
    cin >> n;
    for(int i = 0;i < n;i++)
    cin >> a[i];
    mergesort(a, 0, n - 1);
    for(int i = 0;i < n;i++)
    printf("%d ",a[i]);
    return 0;
}