【建议收藏】数据结构考研常用的8种排序算法-php黑洞网

本站消息

站长简介/公众号

出租广告位,需要合作请联系站长

bbjbbh

2129

文章

861997

访问

+关注

分类

暂无分类

日期归档

2024-11(2)

【建议收藏】数据结构考研常用的8种排序算法

发布于2021-06-07 21:32 阅读(911) 评论(0) 点赞(3) 收藏(1)

排序算法

最近在准备考研，正好在学习数据结构的排序，发现下面这位大佬总结的很详细，不过是用java，我得用c++来考试，所有用c++来总结一下。

大多图片均来自于：
作者：三四月事八九月果
java实现10种排序算法

作者：一像素
十大经典排序算法

c++代码学习：天勤考研

1.冒泡排序

在这里插入图片描述
思路：

1.比较相邻的元素。如果第一个比第二个大，就交换它们两个；
2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
3.针对所有的元素重复以上的步骤，除了最后一个；
4.重复步骤1~3，直到排序完成。

代码：

#include <bits/stdc++.h>
using namespace std;

void bubleSort(int arr[],int n)
{
    int i,j,flag;
    for(i=0;i<n-1;i++)
    {
        flag=0;
        for(int j=0;j<n-1-i;j++)
        {
            if(arr[j]>arr[j+1])
            {
                swap(arr[j],arr[j+1);
                flag=1;
            }
        }
        //如果flag等于0,证明排序已经完成，不需要继续排序
        if(flag==0)
            return;
    }
}

//打印
void printLn(int arr[],int n)
{   
    for(int i=0;i<n;i++)
        cout<<arr[i]<<"  ";
    cout<<endl;
}

int main()
{
    int arr[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
    bubleSort(arr,15);
    printLn(arr,15);
}

2.插入排序

在这里插入图片描述
思路：

当遍历元素为i时，依次与它前面的i-1,i-2等比较大小。
当遇到元素小于遍历元素时，循环停止，记录遍历元素i应该插入的位置。

代码：

#include <bits/stdc++.h>
using namespace std;


void insertSort(int arr[],int n)
{
    for( int i = 1 ; i < n ; i ++ ) {
        int e=arr[i];
        int j; // j保存元素e应该插入的位置
        for (j = i; j > 0 && arr[j-1] > e; j--)
            arr[j] = arr[j-1];
        arr[j] = e;
    }
}

//打印
void printLn(int arr[],int n)
{   
    for(int i=0;i<n;i++)
        cout<<arr[i]<<"  ";
    cout<<endl;
}

int main()
{
    int arr[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
    insertSort(arr,15);
    printLn(arr,15);
}

3.简单选择排序

在这里插入图片描述
思路：

每次遍历依次找出最小值，放到最前面，
然后继续找出它后面剩余元素的最小值，直到剩余元素只有一个时，遍历完成。

代码：

#include <bits/stdc++.h>
using namespace std;

void selectSort(int arr[],int n)
{
    int i,j,k;
    for(i=0;i<n;++i)
    {
        k=i;  //记录最小值
        for(j=k+1;j<n;++j)
            if(arr[k]>arr[j])
                k=j;
        swap(arr[i],arr[k]);
    }
}

//打印
void printLn(int arr[],int n)
{   
    for(int i=0;i<n;i++)
        cout<<arr[i]<<"  ";
    cout<<endl;
}

int main()
{
    int arr[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
    selectSort(arr,15);
    printLn(arr,15);
}

4.希尔排序

图片地址：
作者：the3times
在这里插入图片描述

#include <bits/stdc++.h>
using namespace std;

void shellSort(int arr[],int n)
{
    int temp;
    for(int gap=n/2;gap>0;gap/=2)
    {
        for(int i=gap;i<n;++i)
        {
            temp=arr[i];
            int j;
            for(j=i;j>gap&& arr[j-gap]>temp;j-=gap);
                arr[j]=arr[j-gap];
            arr[j]=temp;
        }
    }
}

//打印
void printLn(int arr[],int n)
{   
    for(int i=0;i<n;i++)
        cout<<arr[i]<<"  ";
    cout<<endl;
}

int main()
{
    int arr[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
    shellSort(arr,15);
    printLn(arr,15);
}

5.快速排序

在这里插入图片描述
思路：

1.从数列中挑出一个元素，称为 “基准”。
2.重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
3.递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

代码：

#include<bits/stdc++.h>
using namespace std;

void quickSort(int arr[],int low,int high)
{
    int temp;
    int i=low,j=high;
    if(low<high)
    {
        temp=arr[low];
        while(i<j)
        {
            while(i<j&&arr[j]>=temp)
                --j;
            if(i<j)
            {
                arr[i]=arr[j];
                ++i;
            }
            while (i<j&&arr[i]<temp)
                ++i;
            if(i<j)
            {
                arr[j]=arr[i];
                --j;
            }
            arr[i]=temp;
            quickSort(arr,low,i-1);
            quickSort(arr,i+1,high);
        }
    }
}

//打印
void printLn(int arr[],int n)
{   
    for(int i=0;i<n;i++)
        cout<<arr[i]<<"  ";
    cout<<endl;
}

int main()
{
    int arr[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
    quickSort(arr,0,14);
    printLn(arr,15);
}

快速代码的改进：
我比较喜欢第一种，看个人喜欢

#include<bits/stdc++.h>
using namespace std;

int _partition(int arr[],int l,int r){
    int v=arr[l];
    int j=l;
    for(int i=l+1;i<=r;i++){
        if(arr[i]<v){
            swap(arr[++j],arr[i]);
        }
    }
    swap(arr[l],arr[j]);
    return j;
}

void _quickSort(int arr[],int l,int r){
    if(l>=r)
        return ;
    int p=_partition(arr,l,r);
    _quickSort(arr,l,p-1);
    _quickSort(arr,p+1,r);
}

void quickSort(int arr[],int n){
    _quickSort(arr,0,n-1);
}

//打印
void printLn(int arr[],int n)
{   
    for(int i=0;i<n;i++)
        cout<<arr[i]<<"  ";
    cout<<endl;
}

int main()
{
    int arr[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
    quickSort(arr,15);
    printLn(arr,15);
}

6.归并排序

在这里插入图片描述
代码：

#include<bits/stdc++.h>
using namespace std;


// 将arr[l...mid]和arr[mid+1...r]两部分进行归并
void _merge(int arr[], int l, int mid, int r){

    int aux[r-l+1];

    for( int i = l ; i <= r; i ++ )
        aux[i-l] = arr[i];

    // 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1
    int i = l, j = mid+1;
    for( int k = l ; k <= r; k ++ ){

        if( i > mid ){  // 如果左半部分元素已经全部处理完毕
            arr[k] = aux[j-l]; j ++;
        }
        else if( j > r ){  // 如果右半部分元素已经全部处理完毕
            arr[k] = aux[i-l]; i ++;
        }
        else if( aux[i-l] < aux[j-l] ) {  // 左半部分所指元素 < 右半部分所指元素
            arr[k] = aux[i-l]; i ++;
        }
        else{  // 左半部分所指元素 >= 右半部分所指元素
            arr[k] = aux[j-l]; j ++;
        }
    }

}

// 递归使用归并排序,对arr[l...r]的范围进行排序
void _mergeSort(int arr[], int l, int r){

    if( l >= r )
        return;
    int mid = (l+r)/2;
    _mergeSort(arr, l, mid); 
    _mergeSort(arr, mid+1, r); 
    _merge(arr, l, mid, r);
}

void mergeSort(int arr[], int n){

    _mergeSort( arr , 0 , n-1 );
}

//打印
void printLn(int arr[],int n)
{   
    for(int i=0;i<n;i++)
        cout<<arr[i]<<"  ";
    cout<<endl;
}

int main()
{
    int arr[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
    mergeSort(arr,15);
    printLn(arr,15);
}

7.基数排序

图片来源
数据结构和算法(二十)基数排序算法
在这里插入图片描述
思路：

1.首先看最大位为多少位，例如最大位1100，则有4位。
2.依次遍历所有数据的个位，十位，百位等进行入“桶”(桶是指1~9)。
当遇到有的元素是2位，有的元素是3位时，可以把十位的数据的前面补0
例如：10 100这些数据，我们可以看成010 100进入依次入“桶”。

代码：

#include <bits/stdc++.h>
using namespace std;



int Max_bit(int arr[],int n)
{
    int maxSize=arr[0];
    for(int i=0;i<n;i++)
        if(maxSize<arr[i])
            maxSize=arr[i];
    return maxSize;
}
void radixSort(int a[],int n)      //基数排序 
{
	queue<int> temp[10];
	int mod=10;
	int div=1;
	int j=0;
	int num=0;
    int max_bit;
    max_bit=Max_bit(a,n);
    string s=to_string(max_bit);
    max_bit=s.size();
	for(int i=0;i<max_bit;i++,mod*=10,div*=10)
	{
		
		for(j=0;j<n;j++)
		{
			num=(a[j]%mod)/div;
			temp[num].push(a[j]);
		}
		int pos=0;
		for(j=0;j<10;j++)
		{
			
			while(!temp[j].empty())
			{
				
				a[pos++]=temp[j].front();
				temp[j].pop();
			}
		}
	}
}

//打印
void printLn(int arr[],int n)
{   
    for(int i=0;i<n;i++)
        cout<<arr[i]<<"  ";
    cout<<endl;
}


int main()
{
    int arr[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
    radixSort(arr,15);
    printLn(arr,15);
}

8.堆排序

建大顶堆：
在这里插入图片描述
代码对应；

每次取出堆中最大的数据：
上面一张的图的作用是为下面做铺垫，因为只有你的数组一开始变为大顶堆的结构，下面这张才能起到作用。上图类似于是下图的初始化。
在这里插入图片描述
代码对应:

思路：
如果对二叉树不了解的可以去看这篇博客
二叉树

1)参数解释
	1.结构为完全二叉树结构
	2.最后一个非叶子结点的下标:n/2-1
	3.左孩子结点下标:2*i+1 右孩子结点下标:2*i+2
	4.堆结构：大顶堆(根结点比左右孩子结点大)
2）首先思路
	1.建立大顶堆结构
	2.每次取出最大值

代码：

#include<bits/stdc++.h>
using namespace std;

void sift(int arr[],int low,int high)
{	
	//j指向的是i的左孩子结点
    int i=low,j=2*i+1;
    int temp=arr[i];
    while(j<high)
    {
    	//比较i的左孩子结点和右孩子结点的大小，谁大就把值赋值给i
        if(j<high && arr[j]<arr[j+1])
            ++j;
        if(temp<arr[j])
        {
        	//把左右孩子结点中大的值赋值给i
            arr[i]=arr[j];
            //把i指向它的孩子结点，把j指向它的左孩子结点
            i=j;
            j=2*i+1;
        }else{
            break;
        }
    }
    arr[i]=temp;
}

void heapSort(int arr[],int n)
{
    int i;
    int temp;
    //n/2-1的作用的指向最后一个非叶子结点
    //下面代码的作用：把二叉树变为大顶堆的结构
    //大顶堆：root结点比左右孩子结点大
 	//1.建大顶堆
    for(i=n/2-1;i>=0;--i)
        sift(arr,i,n-1);
	
	//因为上面求出的大顶堆的下标为0处的值一定的最大的。
	//所以我们可以把下标被0的值与i的值进行交换
	//然后继续让它变为大顶堆，所有它的下标为0处的值一定是最大
	//然后只需要把它和i-1的值进行交换就可以了
	//循环进行，直到i=0时。
	//2.每次取出堆中 最大值
    for(i=n-1;i>0;--i)
    {
        temp=arr[0];
        arr[0]=arr[i];
        arr[i]=temp;
        //把下标为0的值变为最大值
        sift(arr,0,i-1);
    }
}

//打印
void printLn(int arr[],int n)
{   
    for(int i=0;i<n;i++)
        cout<<arr[i]<<"  ";
    cout<<endl;
}

int main()
{
    int arr[]={3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
    heapSort(arr,15);
    printLn(arr,15);
}