排序算法大集结（Sort）

预计阅读时间：10分钟

目录

第一部分：冒泡排序

介绍

过程

代码 

第二部分：选择排序

介绍

过程

代码 

第三部分：插入排序

简介

过程

代码

第四部分：堆排序

简介

过程

代码

第五部分：归并排序

简介

过程

代码

第六部分：快速排序

简介

过程

代码

---

第一部分：冒泡排序

介绍

        冒泡排序（Bubble Sort)的名字由来是因为越小（或者越大）的元素回经由交换慢慢“浮”到数列的顶端，就像气泡一样。

过程

        冒泡排序的执行过程大致是：一次比较相邻的两个数，将小的放在前面，大的放在后面。具体操作步骤：

        1.首先比较第1个数和第2个数，将小的放在前面，大的放在后面。比较第2个数和第3个数，将小的放在前面，大的放在后面，重复执行该操作，直到比较到最后两个数，第一轮结束。

        2.仍然是从第一对数开始比较，将小的放在前面，大的放在后面，一只比较到倒数第2个数，第2轮方可结束。

        3.重复执行上述操作直到完成排序。

        下面是一个动图，大家可以通过这个动图来更好的理解冒泡排序。

代码 

冒泡排序函数，在主函数中调用即可。

int arr[] = { 1,3,5,7,9,2,4,6,8 };   // 待排序数组
int cnt = sizeof(arr) / sizeof(int); // 数组长度
void bubble_sort()
{
	for (int i = 0; i < cnt; ++i) 
	{
		for (int j = 0; j < cnt - 1 - i; ++j) 
		{
			if (arr[j] > arr[j + 1])  // 从小排到大
			{
				int temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}
}

时间复杂度：最坏情况：O(N^2)
      最好情况：O(N)
空间复杂度：O(1) 

第二部分：选择排序

介绍

        选择排序也是一种简单直观的排序算法，工作原理是：开始时在序列中找到最小（大）的元素，放到序列的其实位置作为已排序序列，然后从生于未排序的元素中寻找最小（大）的元素，放到一排序序列的末尾。以此类推，直到所有元素均排序完毕。

过程

        选择排序具体步骤如下

        1.首先定义一个最小是min，用来存放序列的最小值。

        2.第一轮：将第1个数作为最小值赋给min，然后一次比较第2～5个数，比较的数比min小的话，就将其父为min，最后将min和第1个数交换。 

        3.第二轮：此时第1个数已经是最小值了，现在寻找第二个最小值。将第2个数赋给min，然后比较第3～5个数，找出最小值将其和第2个数交换。

        4.重复上述过程。

下面是选择排序的动图

代码 

int n,i,j,a[2000]={5,4,3,2,1};
bool t;
void Selection_sort()
{
	for (i=1;i//从1开始，最后一位不用比
		for (j=i+1;j<=n;j++)
			if (a[i]>a[j])        //a[i]是基本位，a[j]是当前位
				swap(a[i],a[j]);     //交换
}

时间复杂度：最坏情况：O(N^2)
      最好情况：O(N^2)
空间复杂度：O(1) 

第三部分：插入排序

简介

        插入排序是一种简单直观的排序算法，他的工作原理与抓扑克牌非常类似。

        插入排序的工作原理是：对于未排序数据（右手抓到的牌），在一排序序列（左手已经排好序的牌）中从后向前扫描，找到相应位置并插入。插入排序在实现上通常采用in-place排序（即志勇到O(1)的额外空间的排序），因此在从后向前扫描的过程中需要反复将以排序的元素逐步向后移位，为新元素提供插入空间。

过程

        1.从第1个元素开始，该元素可以认为已经被排序。

        2.第1轮：取出下一个元素，在已排序的元素序列中从后向前扫描，如果该元素（一排序）大于新元素，则将该元素移到下一位置，直到找到已排序的元素小于或等于新元素的位置，将新元素插入该位置之后。

        3.第2轮：将元素下移一个位置，利用相似的方法找到位置。

        3.重复上述操作，直到完成排序。

下面是插入排序的动图，大家可以加深印象

代码

void swap(int* a, int* b)
{
	int temp=*a;
	*a=*b;
	*b=temp;
}
void Select_Sort(int* a, int n)
{
	int begin=0,end=n-1;//保存参与单趟排序的第一个数和最后一个数的下标
	while (begin
	{
		int maxi=begin;//保存最大值的下标
		int mini=begin;//保存最小值的下标
		for (int i=begin; i<=end; i++)//找出最大值和最小值的下标
		{
			if(a[i]
			{
				mini=i;
			}
			if(a[i]>a[maxi])
			{
				maxi=i;
			}
		}
		swap(&a[mini],&a[begin]);//最小值放在序列开头
		if(begin==maxi)//防止最大的数在begin位置被换走
		{
			maxi=mini;
		}
		swap(&a[maxi],&a[end]);//最大值放在序列结尾
		begin++;
		end--;
	}
}

时间复杂度：最坏情况下为O(N*N)，此时待排序列为逆序，或者说接近逆序
      最好情况下为O(N)，此时待排序列为升序，或者说接近升序。
空间复杂度：O(1) 

第四部分：堆排序

简介

        对排序是指利用堆这种数据结构所设计的一种选择排序算法。堆是一种近似完全二叉树的结构（通常堆排序是用一维数组实现的），并满足性质：以最大堆为例，其中父节点的值总是大于起孩子节点的值。

过程

        1.用输入的无序数组构建一个最大堆，作为初始的无序区。

        2.把堆顶元素（最大值）和堆尾元素互换。

        3.把堆（无序区）的尺寸缩小1，并调用heapify(A,0)从心得堆顶元素开始对堆进行调整。

        4.重复执行第2步和第3步，直到堆的尺寸为1。

代码

//数组交换;
void swap(int a[],int i,int j)
{
	int temp=a[i];
	a[i]=a[j];
	a[j]=temp;
}
//从上往下heapify（形成堆结构排序）;
void heapify(int tree[],int n,int i)
{
	if(i>=n)
    {
		return;
	}
	int c1=2*i+1;
	int c2=2*i+2;
	int max=i;
	if(c1tree[max])
    {
		max=c1
	}
	if(c2tree[max])
    {
		max=c2
	}
	if(max!=i)
    {
		swap(tree,max,i);
		heapify(tree,n,max);
	}
}
//从下到上构建堆;
void build_heap()
{
	int last_node=n-1;
	int parent=(last_node-1)/2;
	int i;
	for(i=parent; i>=0; i--)
    {
		heapify(tree,n,i);
	}
}
//从小到大;
void heap_sort(int tree[], int n){
	build_heap(tree,n);
	int i;
	for(i=n-1; i>=0; i--)
    {
		swap(tree,i,0);
		heapify(tree,i,0);
	}
}

建堆的时间复杂度为O(N);
向下调整算法的时间复杂度为O(log2N);
所以堆排序的时间复杂度为O(N*log2N);

第五部分：归并排序

简介

        归并排序是创建在归并操作上的一种有效的排序算法，与1945年由冯·诺伊曼提出。

        归并排序的实现分为递归实现与非递归（迭代）实现。递归实现的归并排序是算法设计中分治策略的典型应用，可以讲一个大问题分割成若干个小问题解决，然后用所有小问题的答案解决整个大问题。分递归（迭代）实现的归并排序首先进行的是两两归并，然后是四四归并，接着是八八归并，一只到归并完整个数组。

过程

        1.申请空间，是其大小为两个已排序的序列之和，该空间用来存放合并后的序列

        2.设定两个指针，最初位置分别为两个已排序的序列的起始位置。

        3.比较两个指针所指向的元素，选择相对较小的元素放入合并空间，并移动指针到下一位置。重复该操作直到某一指针直接复制合并到序列尾。

        4.将另一序列剩下的所有元素直接复制合并到序列尾。

​

 这幅图就是归并的过程，大家可以消化一下。

代码

void merge(int *data, int start, int mid, int end, int *result)
{
    int i, j, k;
    i = start;
    j = mid + 1;                        //避免重复比较data[mid]
    k = 0;
    while (i <= mid && j <= end)        //数组data[start,mid]与数组(mid,end]均没有全部归入数组result中去
    {
        if (data[i] <= data[j])         //如果data[i]小于等于data[j]
            result[k++] = data[i++];    //则将data[i]的值赋给result[k]，之后i,k各加一，表示后移一位
        else
            result[k++] = data[j++];    //否则，将data[j]的值赋给result[k]，j,k各加一
    }
    while (i <= mid)                    //表示数组data(mid,end]已经全部归入result数组中去了，而数组data[start,mid]还有剩余
        result[k++] = data[i++];        //将数组data[start,mid]剩下的值，逐一归入数组result
    while (j <= end)                    //表示数组data[start,mid]已经全部归入到result数组中去了，而数组(mid,high]还有剩余
        result[k++] = data[j++];        //将数组a[mid,high]剩下的值，逐一归入数组result
 
    for (i = 0; i < k; i++)             //将归并后的数组的值逐一赋给数组data[start,end]
        data[start + i] = result[i];    //注意，应从data[start+i]开始赋值
}
void merge_sort(int *data, int start, int end, int *result)
{
    if (start < end)
    {
        int mid = start + (end-start) / 2;//避免溢出int
        merge_sort(data, start, mid, result);                    //对左边进行排序
        merge_sort(data, mid + 1, end, result);                  //对右边进行排序
        merge(data, start, mid, end, result);                    //把排序好的数据合并
    }
}
void amalgamation(int *data1, int *data2, int *result)
{
    for (int i = 0; i < 10; i++)
        result[i] = data1[i];
    for (int i = 0; i < 10; i++)
        result[i + 10] = data2[i];
}

时间复杂度：O(nlogn)。

调用merge_sort函数即可。

第六部分：快速排序

简介

        快速排序是由东尼·霍尔所发明的排序算法。事实上，排序算法通常明显比其他算法更快，因为它的内部循环可以在大部分框架上很有效地被实现出来。

过程

        1.从序列中挑选出一个元素，作为基准。

        2.把所有比基准小的元素放在基准的前面，把所有比基准大的元素放在基准的后面（相同的数放到任一边），这个过程称为分区。

        3.对每个分区递归地进行步骤1和步骤2，递归的结束条件是序列的大小是0。

代码

int a[maxn];
void qsort(int left,int right)
{
	if(left>right)
	{
		return;
	}
	int i=left,j=right,temp=a[left];
	while(i
	{
		while(i=temp)
		{
			j--;
		}
		while(i
		{
			i++;
		}
		if(i
		{
			swap(a[i],a[j]);
		}
	}
	swap(a[left],a[i]);
	qsort(left,i-1);
	qsort(i+1,right);
}

好啦，最好用的几种排序算法就都给大家分享完了，希望大家有所收获呀！