[C++]七大经典排序算法详解(代码实现+解析)

作者:MinecraftSep,发表于 Mon Feb 26 2024。

前言:排序是将一组数据,按照指定的顺序或要求来进行排列的过程。是数据结构相关课程和内容较为重要和核心的内容之一,常常作为考试题和面试题目来考察学生和面试者,因此熟练掌握经典的排序算法原理和代码实现是非常重要的 本文介绍了几大较为经典的排序算法:插入、希尔、选择、堆、冒泡、快速和归并排序

各种排序算法动图解析请参考

202ceb2dbe9af3db167f6e079a4317160c7181050244f2d7e6c6bc76bb4ade42.png (1355×904) (zshfoj.com)

各种排序算法复杂度对比 冒泡排序:两两比较,将大的元素不断后移; 选择排序:在一次遍历中,选择最小的元素,和从起始位置开始的元素交换; 插入排序:选择一个元素,若此元素比前一个元素大,while循环不断左移找到它的位置。 希尔排序:在插入排序的基础之上加入了一个gap步长进行排序 归并排序:数组分治,将有序的子数组合并 快速排序:在数组中选择一个基准找到它的位置,接着从基准的两边采用同样的方法分治。 堆排序:先对整个数组构建大顶堆,接着从根节点开始不断调整。

冒泡排序法

冒泡排序是所有排序算法中相对简单且容易理解的算法,它的核心思想:通过for循环不断遍历需要排序的元素,依次比较相邻的两个元素,若不满足指定的顺序(可以从大到小排序,也可以反过来),就交换两个元素,直至完成排序。

void BubbleSort(int arr[], int n)
{
    for (int i = 0; i < n - 1; i++)
	{
            for (int j = 0; j < n - i - 1; j++)
	        {
                    if (arr[j] > arr[j + 1]) 
			{
                            int temp = arr[j];
                            arr[j] = arr[j + 1];
                            arr[j + 1] = temp;
                        }
                 }
         }
}

冒泡排序优化:

用一个bool类型的变量来作为标志位,标记在某一轮遍历中是否发生过元素交换,如果未发生元素交换则证明当前数组已经排序完毕,直接中断此次循环。

void BubbleSort(int arr[], int n)
{
    for (int i = 0; i < n - 1; i++)
	{
			//如果用一个flag来判断当前数组是否已经有序,有序则退出循环
			bool flag = true;
            for (int j = 0; j < n - i - 1; j++)
	        {
                    if (arr[j] > arr[j + 1]) 
					{
                            int temp = arr[j];
                            arr[j] = arr[j + 1];
                            arr[j + 1] = temp;
                            flag = false;
                     }
             }
             if (flag) break;
     }
}

选择排序

选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

void SelectionSort(int arr[],int len)
{
	for(int i = 0; i < len; i++)
	{
		int min = i;
		for(j = i + 1; j < len; j++)
		{
			if(a[j] < a[min])
			min = j;
		}
		int temp = a[min];
		a[min] = a[i];
		a[i] = temp;
	}
}

插入排序

插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

void insertSort(int a[], int n)
{
   for(int i = 1; i < n; i++) //第一个元素作为基准元素,从第二个元素开始把其插到正确的位置
   {
	  if(a[i] < a[i-1]) //如果第i个元素比前面的元素小
	  {
	      int j = i-1;     //需要判断第i个元素与前面的多个元素的大小,换成j继续判断
          int x = a[i]; //将第i个元素复制为哨兵
	      while(j >= 0 && x < a[j]) //找哨兵的正确位置,比哨兵大的元素依次后移
	      {
             a[j+1] = a[j]; 
	         j--;
	      }
	      a[j+1] = x;  //把哨兵插入到正确的位置
	  }   
   }
}

希尔排序

简单插入排序的改进版。它与插入排序的不同之处在于,它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。 先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,具体算法描述:

void shellSort(int a[], int n)  //a -- 待排序的数组, n -- 数组的长度
{
    int i,j,gap;   // gap为步长,每次减为原来的一半。
    for (gap = n / 2; gap > 0; gap /= 2)
    {
        // 共gap个组,对每一组都执行直接插入排序
        for (i = 0 ;i < gap; i++)
        {
            for (j = i + gap; j < n; j += gap) 
            { 
                // 如果a[j] < a[j-gap],则寻找a[j]位置,并将后面数据的位置都后移。
                if (a[j] < a[j - gap])
                {
                    int tmp = a[j];
                    int k = j - gap;
                    while (k >= 0 && a[k] > tmp)
                    {
                        a[k + gap] = a[k];
                        k -= gap;
                    }
                    a[k + gap] = tmp;
                }
            }
        }
    }
}
void shellsort(int arr[], int n) {
	for (int gap = n; gap >= 1; gap /= 2) {
		for (int i = gap; i < n; i += gap) {
			int temp = arr[i];
			int pre = i - gap;
			while (pre >= 0 && arr[pre] > temp) {
				arr[i] = arr[pre];
				pre -= gap;
			}
			arr[pre + gap] = temp;
		}
	}
}

归并排序

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。

/* 初始版本,升序排序 */
/* 时间复杂度:O(nlbn) 将n个待排序记录归并次数为lbn,一趟归并O(n)
   空间复杂度:O(n) 递归栈最大深度为[lbn] + 1 ,而辅助数组大小为n
   稳定:无论最好还是最坏情况时间复杂度都是O(nlbn)
*/
 
void Merge(int arr[], int n)
{
    int temp[n]; // 用一个额外的数组来进行排序
    int b = 0; // 额外数组的起始位置
    int mid = n / 2; // mid将数组从中间划分,前后两半都有序
    int first = 0, second = mid; // 两个有序序列的起始位置
 	//以下操作类似于将两个数组合并为一个有序数组
    while (first < mid && second < n)
    {
        if (arr[first] <= arr[second]) // 比较两个序列
        	//这步操作相当于把第一个数组的值放到用来排序的数组,接着两个指针后移对下一个值进行操作
            temp[b++] = arr[first++];
        else
            temp[b++] = arr[second++];
    }
 
    while(first < mid)  // 将剩余子序列复制到辅助序列中
            temp[b++] = arr[first++];
    while(second < n)
            temp[b++] = arr[second++];
    for (int i = 0; i < n; ++i) // 辅助序列复制到原序列
        arr[i] = temp[i];
}
 
void MergeSort(int arr[], int n)
{
    if (n <= 1) // 递归出口
        return;
    if (n > 1)
    {
        MergeSort(arr, n / 2); // 对前半部分进行归并排序
        MergeSort(arr + n / 2, n - n / 2); // 对后半部分进行归并排序
        Merge(arr, n); // 归并两部分
    }
}

快速排序(Quick Sort)

快速排序的基本思想:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。 快速排序使用分治法来把一个串(list)分为两个子串(sub-lists)。具体算法描述如下:

void Quicksort(int arr[], int low, int high) {
	if (low < high) {
		//双指针,一个指向数组起始,一个指向数组末尾
		int i = low;
		int j = high;
		//将数组的第一个元素作为key寻找它的位置
		//key找到它的位置后,以它为分界线,左右两个数组分治
		int key = arr[i];
		while (i < j) {
			//两个指针不相遇,且指针指向的值大于key时,不断左移
			while (i < j && arr[j] >= key)
				j--;
			if (i < j) arr[i] = arr[j];
			//两个指针不相遇,且指针指向的值小于key时,不断右移
			while (i < j && arr[i] <= key)
				i++;
			if (i < j) arr[j] = arr[i];
		}
		//将key放在适合的位置
		arr[i] = key;
		//分治
		Quicksort(arr, low, i - 1);
		Quicksort(arr, i + 1, high);
	}
}

堆排序(Heap Sort)

堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

// Heapsort.cpp : 定义控制台应用程序的入口点。
//
 
#include "stdafx.h"
#include<iostream>
using namespace std;
void swap(int arr[], int a, int b)		//交换元素;
{
	int temp = arr[a];
	arr[a] = arr[b];
	arr[b] = temp;
}
void adjustHeap(int arr[], int i, int length)		//调整大顶堆(仅是调整过程,建立在大顶堆已构建的基础上)
{
	int temp = arr[i];//先取出当前元素i
	for (int k = i * 2 + 1; k<length; k = k * 2 + 1)//从i结点的左子结点开始,也就是2i+1处开始
	{
		if (k + 1<length&&arr[k]<arr[k + 1])//如果左子结点小于右子结点,k指向右子结点
		{
			k++;
		}
		if (arr[k] >temp)//如果子节点大于父节点,将子节点值赋给父节点(不用进行交换)
		{
			arr[i] = arr[k];
			i = k;
		}
		else
		{
			break;
		}
	}
	arr[i] = temp;//将temp值放到最终的位置
}
void Heapsort(int arr[], int length)
{
	//1.构建大顶堆
	for (int i = length / 2 - 1; i >= 0; i--)
	{
		//从第一个非叶子结点从下至上,从右至左调整结构
		adjustHeap(arr, i, length);
	}
	for (int j = length - 1; j>0; j--)
	{
		swap(arr, 0, j);//将堆顶元素与末尾元素进行交换
		adjustHeap(arr, 0, j);//重新对堆进行调整
	}
 
}
int main()
{
	int arr[9] = { 9,8,7,6,10,4,3,2,1 };
	Heapsort(arr, 9);
	for (int i = 0; i<9; i++)
		cout << arr[i] << " ";
	cout << endl;
	return 0;
}

Copyright © 2024 LVJ, Open-Source Project. 本站内容在无特殊说明情况下均遵循 CC-BY-SA 4.0 协议,内容版权归属原作者。