十大排序算法(数据结构)排序内部排序

71 阅读 0 评论 47 点赞

我是靠谱客的博主漂亮月饼，最近开发中收集的这篇文章主要介绍十大排序算法(数据结构)排序内部排序，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

排序

文章目录

排序
内部排序
- 一、插入排序
- - 1.直接插入排序
  - 2.折半插入排序
  - 3.希尔排序
- 二、交换排序
- - 1.冒泡排序
  - 2.快速排序
- 三、选择排序
- - 1.简单选择排序
  - 2.堆排序
- 四、归并排序和基数排序
- - 1.二路归并排序（merge sort）
  - 2.桶排序(计数排序)
  - 3,基数排序
- 五、王道中的实现细节
- - 1.快速排序
  - 2.堆排序(非递归)
  - 3.归并排序
  - 4.基数排序

内部排序

一、插入排序

基本思想：每次将一个待排序的记录按其关键字大小插入前面已经排好序的子序列中。

1.直接插入排序

给定一个整数数组 q[]，将该数组升序排列。

以第一个元素作为有序数组，其后的元素通过在这个已有序的数组中找到合适的位置并插入
a. 时间复杂度
		[1] 最好情况：O(n)
		[2] 平均情况：O(n^2)
		[3] 最坏情况：O(n^2)
b. 辅助空间复杂度      O(1)
c. 稳定性：           稳定
void insert_sort()
{
    for(int i = 1;i < n; i ++ ) //0~i-1已经有序
    {
        int t = q[i], j;//i位置元素待插入
        for(j = i-1; j>=0 && q[j] > t; j -- ){ //向前寻找插入位置
            if(q[j] > t) q[j+1] = q[j];
        }
        q[j+1] = t; //插入
    }
}

2.折半插入排序

给定一个整数数组 q[]，将该数组升序排列。

与直接插入排序的唯一区别就是 查找插入位置时 使用二分，复杂度不变
a. 时间复杂度
		[1] 最好情况：O(n)
		[2] 平均情况：O(n^2)
		[3] 最坏情况：O(n^2)
b. 辅助空间复杂度      O(1)
c. 稳定性：           稳定

void binary_search_insert_sort() 
{
    for(int i = 1; i < n; i ++ ) //0~i-1已经有序
    {
        if(q[i]>=q[i-1]) continue; 
        int t = q[i];//i位置元素待插入
        
        int l = 0, r = i-1;
        while(l < r)  //二分寻找插入位置(大于t的第一个位置)
        {
            int mid = (l+r)>>1;
            if(q[mid] > t) r=mid;
            else l=mid+1;
        }
        
        for(int j = i-1; j >= r ;j--) q[j+1]=q[j];
        q[r]=t;//插入
    }
}

3.希尔排序

给定一个整数数组 q[]，将该数组升序排列。

类插入排序，只是向前移动的步数变成d，分别在各组内进行 直接插入排序
a. 时间复杂度         O(n^(3/2))
b. 辅助空间复杂度      O(1)
c. 稳定性：           不稳定(分组导致)

void shell_sort()  // 希尔排序
{
    for(int d = n/2; d >= 1; d /= 2)//步长
    {
        for(int start = 0; start < d; start ++)//分组(分别进行直接插入排序)
        {
            for(int j = start+d; j < n; j += d)//直接插入排序
            {
                int t = q[j],k;
                for(k = j-d; k >=0 && q[k] > t; k -= d){
                    q[k+d]=q[k];
                }
                q[k+d]=t;
            }
        }
    }
}

二、交换排序

基本思想：根据比较两个关键字结果来对换其位置(每次确定一个元素的最终位置)

1.冒泡排序

给定一个整数数组 nums，将该数组升序排列。

通过相邻元素的比较和交换，使得每一趟循环都能找到未有序数组的最小值(从后往前)
a. 时间复杂度
		[1] 最好情况：O(n) 
		[2] 平均情况：O(n^2)
		[3] 最坏情况：O(n^2)
b. 辅助空间复杂度      O(1)
c. 稳定性：           稳定

 void bubble_sort()  // 冒泡排序
{
    for(int i = 0; i < n-1; i ++ ) //0~i-1已经有序
    {
        bool has_swap = false;
        for(int j = n-1; j > i; j -- ){ //从后往前冒泡
            if(q[j] < q[j-1]) swap(q[j],q[j-1]),has_swap=true;
        }
        if(!has_swap) return ;//没有交换说明已经有序
    }
}

2.快速排序

给定一个整数数组 q[]，将该数组升序排列。

基于分治思想
选择中间点为分界点，使得左边的数<=x,右边的数>=x
最后再递归左右两边

a. 时间复杂度
		[1] 最好情况：O(nlogn)
		[2] 平均情况：O(nlogn)
		[3] 最坏情况：O(n^2)   数组逆序且选择边界点为分界点时
b. 辅助空间复杂度      O(logn)
c. 稳定性：           不稳定


void quick_sort(int l, int r)  // 快速排序
{
    if(l>=r) return ;
    int i = l-1,  j= r+1, x=q[(l+r)/2];
    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(l,j);
    quick_sort(j+1,r);
}

三、选择排序

基本思想：每一趟都从待排序的元素中选取最小(或最大)的元素加入有序子序列

1.简单选择排序

给定一个整数数组 q[]，将该数组升序排列。

每次从未排序中找到最小的元素放到当前位置
a. 时间复杂度
		[1] 最好情况：O(n^2)
		[2] 平均情况：O(n^2)
		[3] 最坏情况：O(n^2)   
b. 辅助空间复杂度      O(1)
c. 稳定性：           不稳定

void select_sort()  // 简单选择排序
{
    for(int i = 0; i < n; i ++)
    {
        int k=i;
        for(int j = i+1; j < n ;j++){
             if(q[j]<q[k]) k=j;
        }
        swap(q[k],q[i]);
    }
}

2.堆排序

给定一个整数数组 q[]，将该数组升序排列。

是一棵采用顺序存储的完全二叉树，从下往上建图，down()操作：建立以当前结点为根的大根堆
a. 时间复杂度
		[1] 最好情况：O(nlogn)
		[2] 平均情况：O(nlogn)
		[3] 最坏情况：O(nlogn)   
b. 辅助空间复杂度      O(logn)
c. 稳定性：           不稳定
void down(int u)
{
    int t=u;
    if(u*2 <= sz && q[u*2] > q[t]) t = u*2;
    if(u*2+1 <= sz && q[u*2+1] > q[t]) t=u*2+1;
    
    if(t != u)
    {
        swap(q[t],q[u]);
        down(t);
    }
}
void heap_sort()  // 堆排序(大根堆)，下标一定要从1开始
{
    sz=n;
    for(int i = n/2; i; i--) down(i);
    
    for(int j = 0; j < n-1 ; j ++) //堆的删除
    {
        swap(q[1],q[sz]);
        sz--;
        down(1);
    }
}

四、归并排序和基数排序

1.二路归并排序（merge sort）

//基于分治思想
//1.[L,R]=> [L,mid],[mid+1,R]
//2.递归排序[L,mid],[mid+1,r]
//3.归并，将左右两个有序序列合并成一个有序序列

a. 时间复杂度
		[1] 最好情况：O(nlogn)
		[2] 平均情况：O(nlogn)
		[3] 最坏情况：O(nlogn)   
b. 辅助空间复杂度      O(n)
c. 稳定性：           稳定

void merge_sort(int l, int r) //二路归并排序
{
    if(l>=r) return ;
    int mid = (l+r)>>1;
    merge_sort(l,mid),merge_sort(mid+1,r);
    int i = l, j = mid+1, k=0;
    while(i<=mid&&j<=r)
    {
        if(q[i]<=q[j]) w[k++]=q[i++];
        else w[k++] = q[j++];
    }
    while(i<=mid) w[k++] = q[i++];
    while(j<=r)   w[k++] = q[j++];
    
    for(int i = l,j = 0; j < k; i ++, j ++) q[i]=w[j];
}

2.桶排序(计数排序)

//数据范围为m
//开m个桶，分别记录每个元素的个数(又称计数排序)
//求m个桶的前缀和S[i]
//从后往前遍历数组元素，把元素放入最终位置上(大于等于q[i]的元素个数就是元素q[i]的最终位置)
	(1) 时间复杂度
		a. 最好情况：O(n + m)
		b. 平均情况：O(n + m)
		c. 最坏情况：O(n + m)
	(2) 空间复杂度
		O(n + m)
	(3) 稳定

void bucket_sort()   //桶排序
{
    for(int i=0;i<n;i++) s[q[i]]++; //开m个桶，计算每个桶的元素个数
    for(int i=1;i<N;i++) s[i]+=s[i-1];//前缀和
    for(int i=n-1;i>=0;i--) w[--s[q[i]]]=q[i];//计算元素的最终位置((s[q[i]]-1)即为q[i]的最终位置)
    
    for(int i=0;i<n;i++) q[i]=w[i];
}

3,基数排序

基数排序是桶排序的特例，优势是可以处理浮点数和负数，劣势是还要配合别的排序函数

将关键字转化为r进制数,把r进制的各位存入有序数组中，对其进行多关键字排序
由于r进制的每位的大小都是0~r-1,可以对其进行桶排序(O(n+r))
    对已经转化为r进制的关键字
           从r进制的低位到高位  分别进行k次桶排序(k为r进制的位数)  --O(k(n+r))
        (1) 时间复杂度
		a. 最好情况：O(d(n+r))
		b. 平均情况：O(d(n+r))
		c. 最坏情况：O(d(n+r))
	(2) 空间复杂度
		O(n + r)
	(3) 稳定(因为桶排序稳定)
    
void radix_sort(int d,int r)  //基数排序（d表示r进制下有几位数）
{
    int radix=1;//r进制下的第一位
    for(int i = 1; i <= d; i++)  //从低位到高位
    {
        //对r进制的每位分别进行桶排序(以下5行为桶排序的操作)
        for(int j = 0; j < r; j ++ ) s[j] = 0;//r个桶清零(r进制下每位大小范围0~r-1)
        for(int j = 0; j < n; j ++ ) s[q[j] / radix % r] ++; //桶排序的计数
        for(int j = 1; j < r; j ++ ) s[j] += s[j - 1];//前缀和
        for(int j = n-1; j >= 0; j -- ) w[ -- s[q[j] / radix % r]] = q[j];//计算元素的位置
        for(int j = 0; j < n; j ++ ) q[j] = w[j];
        
        radix *= r;//处理r进制的下一位
    }
}

    radix_sort(10,10); //10进制  数据范围10^10所以d=10