算法基础之排序

心已赠人 2022-09-08 11:47 124阅读 0赞

### 算法基础之排序（C++示例） ###

排序算法（Sorting algorithm）简称排序（Sort）是一种能将一组特定的数据按某种顺序进行排列的算法。排序算法多种多样，常见的内部排序算法有：插入排序（Insertion sort）、希尔排序（Shell sort）、选择排序（Selection sort）、冒泡排序（Bubble sort）、归并排序（merge sort）、快速排序（Quick sort）、堆排序（Heap sort）、基数排序（Radix sort）、计数排序（Counting sort）、桶排序（Bucket sort）等。

**冒泡排序**

冒泡排序在扫描过程中两两比较相邻数据元素，如果反序则交换，最终，最大数据元素就被“沉到”了序列的最后一个位置，第二遍扫描将第二大数据元素“沉到”了倒数第二个位置，重复上述操作，直到n-1 遍扫描后，整个序列就排好序了。在算法的执行过程中，较小的元素像是气泡般慢慢“浮”到数列的顶端，故叫做冒泡排序。

示例源码:

#include <iostream>
    using namespace std;
    void bubble_sort(int arr[], int len) {
            int i, j, temp;
            for (i = 0; i < len - 1; i++)
                    for (j = 0; j < len - 1 - i; j++)
                            if (arr[j] > arr[j + 1]) {
                                    temp = arr[j];
                                    arr[j] = arr[j + 1];
                                    arr[j + 1] = temp;
                            }
    }
    int main() {
            int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
            int len = (int) sizeof(arr) / sizeof(*arr);
            bubble_sort(arr, len);
            int i;
            for (i = 0; i < len; i++)
                cout << arr[i] << ' ';
            return 0;
    }

**选择排序**

选择排序也是一种简单直观的排序算法。它的工作原理很容易理解：初始时在序列中找到最小（大）元素，放到序列的起始位置作为已排序序列；然后，再从剩余未排序元素中继续寻找最小（大）元素，放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

注意：选择排序与冒泡排序的区别：冒泡排序通过依次交换相邻两个顺序不合法的元素位置，从而将当前最小（大）元素放到合适的位置；而选择排序每遍历一次都记住了当前最小（大）元素的位置，最后仅需一次交换操作即可将其放到合适的位置。

示例源码:

#include <iostream>
    using namespace std;
    
    void SelectSort(int a[],int len)
    {
    	//外层循环跑n趟
     
    	for (int i = 0; i < len; i++){ 
    		//内层循环找出最小值进行交换
    		int tmp;
    		for (int j = i; j < len; j++){ 
    			if (a[j] < a[i]){
    				tmp = a[j];
    				a[j] = a[i];
    				a[i] = tmp;
    			}
    		}
    	}
    }
    
    int main() {
            int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
            int len = (int) sizeof(arr) / sizeof(*arr);
            SelectSort(arr, len);
            int i;
            for (i = 0; i < len; i++)
                cout << arr[i] << ' ';
            return 0;
    }

**插入排序**

其基本思想如下：

对于一个数组A\[0,n\]的排序问题，假设认为数组在A\[0,n-1\]排序的问题已经解决了。

考虑A\[n\]的值，从右向左扫描有序数组A\[0,n-1\]，直到第一个小于等于A\[n\]的元素，将A\[n\]插在这个元素的后面。

示例源码:

#include <iostream>
    using namespace std;
    
    void InsertSort(int a[], int len)
    {
    	int i, j, k; 
    	int tmp;
    	for (i = 1; i < len; i++)	{ 
    		k = i;			//待插入元素位置
    		tmp = a[k];	    //先拿出来
     
    		for (j = i - 1; (j >= 0) && (a[j] > tmp); j--){
    			a[j + 1] = a[j];			//只要大，则元素后移
    			k = j;						//记录移动的位置
    		} 
    		a[k] = tmp;		//元素插入 
    	} 
    }
    
    int main() {
            int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
            int len = (int) sizeof(arr) / sizeof(*arr);
            InsertSort(arr, len);
            int i;
            for (i = 0; i < len; i++)
                cout << arr[i] << ' ';
            return 0;
    }

**希尔排序**

希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本。

希尔排序是把数据元素按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

简单插入排序很循规蹈矩，不管数组分布是怎么样的，依然一步一步的对元素进行比较，移动，插入，比如\[5,4,3,2,1,0\]这种倒序序列，数组末端的0要回到首位置很是费劲，比较和移动元素均需n-1次。而希尔排序在数组中采用跳跃式分组的策略，通过某个增量将数组元素划分为若干组，然后分组进行插入排序，随后逐步缩小增量，继续按组进行插入排序操作，直至增量为1。希尔排序通过这种策略使得整个数组在初始阶段达到从宏观上看基本有序，小的基本在前，大的基本在后。然后缩小增量，到增量为1时，其实多数情况下只需微调即可，不会涉及过多的数据移动。

示例源码:

#include <iostream>
    using namespace std;
    
    
    void ShellSort(int a[], int len)
    {
    	int i, j, k, tmp;
    	int gap = len;
     
    	do{	
    		//gap的选择可以有多中方案，如gap = gap/2,这里使用的是业界统一实验平均情况最好的，收敛为1
    		gap = gap / 3 + 1;
    		for (i = gap; i < len; i += gap)  //分成len/gap组
    		{
    			//每组使用插入排序
    			k = i;
    			tmp = a[k];
    			for (j = i - gap; (j >= 0) && (a[j] > tmp); j -= gap){
    				a[j + gap] = a[j];
    				k = j;
    			}
    			a[k] = tmp; 
    		}
    	} while (gap > 1);
     
    }
    
    int main() {
            int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
            int len = (int) sizeof(arr) / sizeof(*arr);
            ShellSort(arr, len);
            int i;
            for (i = 0; i < len; i++)
                cout << arr[i] << ' ';
            return 0;
    }

**归并排序**

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。

示例源码:

#include<iostream>
    using namespace std;
    
    void Merge(int A[],int low,int mid,int high)//合并函数
    {
        int *B=new int[high-low+1];//申请一个辅助数组
        int i=low,j=mid+1,k=0;
        while(i<=mid&&j<=high) {//按从小到大存放到辅助数组B[]中
            if(A[i]<=A[j])
                B[k++]=A[i++];
            else
                B[k++]=A[j++];
        }
        while(i<=mid) B[k++]=A[i++];//将数组中剩下的元素放置B中
        while(j<=high) B[k++]=A[j++];
        for(i=low,k=0;i<=high;i++)
            A[i]=B[k++];
        delete []B;//释放空间
    }
    
    void MergeSort(int A[],int low,int high)//合并排序
    {
        if(low<high)
        {
            int mid=(low+high)/2;//取中点
            MergeSort(A,low,mid);//对A[low:mid]中的元素合并排序
            MergeSort(A,mid+1,high);//对A[mid+1:high]中的元素合并排序
            Merge(A,low,mid,high);//合并
        }
    }
    
    int main()
    {
    	int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
        int len = (int) sizeof(arr) / sizeof(*arr);
          
        MergeSort(arr,0,len-1);
        cout<<"排序结果："<<endl;
        for(int i=0;i<len;i++)
           cout<<arr[i]<<" ";
        cout<<endl;
        return 0;
    }

**快速排序**

从数组中选择一个元素，我们把这个元素称之为中轴元素，然后把数组中所有小于中轴元素的元素放在其左边，所有大于或等于中轴元素的元素放在其右边，显然，此时中轴元素所处的位置的是有序的。也就是说，我们无需再移动中轴元素的位置。

从中轴元素那里开始把大的数组切割成两个小的数组(两个数组都不包含中轴元素)，接着我们通过递归的方式，让中轴元素左边的数组和右边的数组也重复同样的操作，直到数组的大小为1，此时每个元素都处于有序的位置。

示例源码:

#include<iostream>
    using namespace std;
    
    int Partition(int r[],int low,int high)//划分函数
    {
        int i=low,j=high,pivot=r[low];//基准元素
        while(i<j)
        {
            while(i<j&&r[j]>pivot) j--;//向左扫描
            if(i<j)
                swap(r[i++],r[j]);//r[i]和r[j]交换后i+1右移一位
            while(i<j&&r[i]<=pivot) i++;//向右扫描
            if(i<j)
                swap(r[i],r[j--]);//r[i]和r[j]交换 后j-1左移一位
        }
        return i;//返回最终划分完成后基准元素所在的位置
    }
    
    int Partition2(int r[],int low,int high)//划分函数
    {
        int i=low,j=high,pivot=r[low];//基准元素
        while(i<j)
        {
            while(i<j&&r[j]>pivot) j--;//向左扫描
            while(i<j&&r[i]<=pivot) i++;//向右扫描
            if(i<j)
                swap(r[i++],r[j--]);//r[i]和r[j]交换
        }
        if(r[i]>pivot)
        {
            swap(r[i-1],r[low]);//r[i-1]和r[low]交换
            return i-1;//返回最终划分完成后基准元素所在的位置
        }
        swap(r[i],r[low]);//r[i]和r[low]交换
        return i;//返回最终划分完成后基准元素所在的位置
    }
    
    void QuickSort(int R[],int low,int high)//实现快排算法
    {
        int mid;
        if(low<high)
        {
            mid=Partition(R,low,high); //基准位置
            QuickSort(R,low,mid-1);//左区间递归快排
            QuickSort(R,mid+1,high);//右区间递归快排
        }
    }
    
    int main()
    {
        int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
        int len = (int) sizeof(arr) / sizeof(*arr);
          
        QuickSort(arr,0,len-1);
        cout<<"排序结果："<<endl;
        for(int i=0;i<len;i++)
           cout<<arr[i]<<" ";
        cout<<endl;
        return 0;
    }

**堆排序**

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

大顶堆（最大堆）：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；

小顶堆（最小堆）：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

堆排序就是把堆顶的元素与最后一个元素交换，交换之后破坏了堆的特性，我们再把堆中剩余的元素再次构成一个大顶堆，然后再把堆顶元素与最后第二个元素交换....如此往复下去，等到剩余的元素只有一个的时候，此时的数组就是有序的了。

示例源码:

#include<iostream>
    using namespace std;
    
    void max_heapify(int arr[], int start, int end) {
        // 建立父节点指标和子节点指标
        int dad = start;
        int son = dad * 2 + 1;
        while (son <= end) { // 若子节点指标在范围内才做比较
            if (son + 1 <= end && arr[son] < arr[son + 1]) // 先比较两个子节点大小，选择最大的
                son++;
            if (arr[dad] > arr[son]) // 如果父节点大于子节点代表调整完毕，直接跳出函数
                return;
            else { // 否则交换父子内容再继续子节点和孙节点比较
                swap(arr[dad], arr[son]);
                dad = son;
                son = dad * 2 + 1;
            }
        }
    }
    
    void heap_sort(int arr[], int len) {
        // 初始化，i从最后一个父节点开始调整
        for (int i = len / 2 - 1; i >= 0; i--)
            max_heapify(arr, i, len - 1);
        // 先将第一个元素和已经排好的元素前一位做交换，再从新调整(刚调整的元素之前的元素)，直到排序完毕
        for (int i = len - 1; i > 0; i--) {
            swap(arr[0], arr[i]);
            max_heapify(arr, 0, i - 1);
        }
    }
    
    int main() {
        int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
        int len = (int) sizeof(arr) / sizeof(*arr);
        heap_sort(arr, len);
        for (int i = 0; i < len; i++)
            cout << arr[i] << ' ';
        cout << endl;
        return 0;
    }

**基数排序**

基数排序的排序思路是这样的：先以个位数的大小来对数据进行排序，接着以十位数的大小来多数进行排序，接着以百位数的大小......

排到最后，就是一组有序的元素了。不过，他在以某位数进行排序的时候，是用“桶”来排序的。

由于某位数（个位/十位....，不是一整个数）的大小范围为0-9，所以我们需要10个桶，然后把具有相同数值的数放进同一个桶里，之后再把桶里的数按照0号桶到9号桶的顺序取出来，这样一趟下来，按照某位数的排序就完成了。

示例源码:

#include<iostream>
    using namespace std;
    
    //*求数据的最大位数,决定排序次数
    int maxbit(int data[], int n) 
    {
        int d = 1; //保存最大的位数
        int p = 10;
        for(int i = 0; i < n; ++i)
        {
            while(data[i] >= p)
            {
                p *= 10;
                ++d;
            }
        }
        return d;
    }
    void radixsort(int data[], int n) //基数排序
    {
        int d = maxbit(data, n);
        int tmp[n];
        int count[10]; //计数器
        int i, j, k;
        int radix = 1;
        for(i = 1; i <= d; i++) //进行d次排序
        {
            for(j = 0; j < 10; j++)
                count[j] = 0; //每次分配前清空计数器
            for(j = 0; j < n; j++)
            {
                k = (data[j] / radix) % 10; //统计每个桶中的记录数
                count[k]++;
            }
            for(j = 1; j < 10; j++)
                count[j] = count[j - 1] + count[j]; //将tmp中的位置依次分配给每个桶
            for(j = n - 1; j >= 0; j--) //将所有桶中记录依次收集到tmp中
            {
                k = (data[j] / radix) % 10;
                tmp[count[k] - 1] = data[j];
                count[k]--;
            }
            for(j = 0; j < n; j++) //将临时数组的内容复制到data中
                data[j] = tmp[j];
            radix = radix * 10;
        }
    }
    
    int main() {
        int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
        int len = (int) sizeof(arr) / sizeof(*arr);
        radixsort(arr, len);
        for (int i = 0; i < len; i++)
            cout << arr[i] << ' ';
        cout << endl;
        return 0;
    }

**计数排序**

计数排序是一种适合于最大值和最小值的差值不是不是很大的排序。

基本思想：就是把数组元素作为数组的下标，然后用一个临时数组统计该元素出现的次数，例如 temp\[i\] = m, 表示元素 i 一共出现了 m 次。最后再把临时数组统计的数据从小到大汇总起来，此时汇总起来是数据是有序的。

示例源码:

#include<iostream>
    using namespace std;
    
    void CountingSort(int array[], int n)
    {
    	int i;
    	int largest = array[0];  //设最初最大元素默认是array[0]
    	int *temp = new int[n];  //申请一个n个int元素的数组内存
     
    	for (i = 1; i < n; i++)
    	{
    		if (largest < array[i])  //找出最大元素
    		{
    			largest = array[i];
    		}
    	}
     
    	int *count = new int[largest + 1];  //申请一个[largest+1]个int元素的数组内存
    	for (i = 0; i <= largest; i++)
    	{
    		count[i] = 0;  //初始化
    	}
     
    	for (i = 0; i < n; i++)
    	{
    		count[array[i]]++;  //计算array数组每个元素出现的次数
    	}
     
    	for (i = 1; i <= largest; i++)
    	{
    		count[i] = count[i - 1] + count[i];  //count数组元素出现次数的累加
    	}
     
    	for (i = n - 1; i >= 0; i--)
    	{
    		temp[count[array[i]] - 1] = array[i];  //将array[]数组的元素赋给已经排好位置的temp[]数组
    		count[array[i]]--;  //数组元素的总次数减少
    	}
     
    	for (i = 0; i < n; i++)
    	{
    		array[i] = temp[i];  //将排好顺序的元素赋给array[]数组
    	}
     
    	delete[] count;  //释放内存
    	count = NULL;
    	delete[] temp;  //释放内存
    	temp = NULL;
    }
    
    int main() {
        int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
        int len = (int) sizeof(arr) / sizeof(*arr);
        CountingSort(arr, len);
        for (int i = 0; i < len; i++)
            cout << arr[i] << ' ';
        cout << endl;
        return 0;
    }

**桶排序**

桶排序的思想是我们首先要知道所有待排序的数的数据范围，知道里面的最大值和最小值各是多少。然后利用最大值和最小值分成若干个桶（数据区间），将所有待排序的数按照其大小分到这些桶（数据区间）中。在每个桶中分别利用排序算法进行排序，这样就完成了所有数据的排序。

示例源码:

#include <iostream>
    using namespace std;
    
    void bucketSort(int arr[], int len) {
        // 确定最大值和最小值
        int max = INT_MIN; int min = INT_MAX;
        for (int i = 0; i < len; i++) {
            if (arr[i] > max) max = arr[i];
            if (arr[i] < min) min = arr[i];
        }
      
        // 生成桶数组
        // 设置最小的值为索引0，每个桶间隔为1
        int bucketLen = max - min + 1;
        // 初始化桶
        int bucket[bucketLen];
        for (int i = 0; i < bucketLen; i++) bucket[i] = 0;
      
        // 放入桶中
        int index = 0;
        for (int i = 0; i < len; i++) {
            index = arr[i] - min;
            bucket[index] += 1;
        }
      
        // 替换原序列
        int start = 0;
        for (int i = 0; i < bucketLen; i++) {
            for (int j = start; j < start + bucket[i]; j++) {
                arr[j] = min + i;
            }
            start += bucket[i];
        }
    }
      
    int main() {
     int arr[] =  { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
     int len = (int) sizeof(arr) / sizeof(*arr);
     bucketSort(arr, len);
     for (int i = 0; i < len; i++) {
     cout << arr[i] << " ";
     }
     cout << endl;
     return 0;
    }

**参考**

[https://zhuanlan.zhihu.com/p/57088609][https_zhuanlan.zhihu.com_p_57088609]

[https://www.runoob.com/w3cnote/ten-sorting-algorithm.html][https_www.runoob.com_w3cnote_ten-sorting-algorithm.html]

[https_zhuanlan.zhihu.com_p_57088609]: https://zhuanlan.zhihu.com/p/57088609
[https_www.runoob.com_w3cnote_ten-sorting-algorithm.html]: https://www.runoob.com/w3cnote/ten-sorting-algorithm.html