排序方法总结

╰半夏微凉° 2022-01-16 12:27 148阅读 0赞

### 排序总结 ###

*  冒泡排序
 *   *  冒泡排序介绍
     *  冒泡排序步骤:
     *  c++源代码
     *   *  基础版
         *  优化版
         *  泛型设计
 *  选择排序(简单选择排序)
 *   *  选择排序介绍
     *  选择排序步骤：
     *  c++源代码
 *  插入排序
 *   *  插入排序介绍
     *  直接插入排序步骤
     *  c++源代码
 *  归并排序
 *   *  归并排序介绍
     *  归并排序步骤
     *  c++源代码
 *  快速排序
 *   *  快速排序介绍
     *  快速排序步骤
     *  c++ 源代码
     *   *  递归版
         *  非递归
 *  堆排序
 *   *  堆排序介绍
     *  堆排序步骤
     *  c++ 源代码
 *  计数排序
 *   *  计数排序介绍
     *  计数排序步骤
 *  桶排序
 *   *  桶排序介绍
     *  桶排序步骤
 *  基数排序
 *   *  基数排序介绍
     *  基数排序步骤
 *  排序方法分析

# 冒泡排序 #

## 冒泡排序介绍 ##

冒泡排序（Bubble Sort）:
    是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个  
    元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直
    到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为
    越小的元素会经由交换慢慢"浮"到数列的顶端。

## 冒泡排序步骤: ##

从小大进行排序：
    
    1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
    2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
    3. 针对所有的元素重复以上的步骤，除了最后一个。
    4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

## c++源代码 ##

### 基础版 ###

void BubbleSort(int a[],int n){ 
 for(int i=0;i<n;i++){ 
 for(int j=0;j<n-i-1;j++){ //-1为了防止溢出
 if(a[j]>a[j+1]){ 
 int t=a[j];
 a[j]=a[j+1];
 a[j+1]=t;
 }
 }
 }
 }

### 优化版 ###

void BubbleSort(int a[],int n){ 
 bool flag= true;
 for(int i=0;i<n-1&&flag;i++){ 
 flag = false;
 for(int j=0;j<n-i-1;j++){ 
 if(a[j]>a[j+1])swap(a[j],a[j+1]),flag= true;
 }
 }
 }

### 泛型设计 ###

#include <bits/stdc++.h>
 using namespace std;
 
 template <class T>
 void Swap(T &a,T &b){ 
 T c=a;
 a=b;
 b=c;
 }
 
 template <class T>
 bool cmp(T a,T b){ 
 return a>b;
 }
 
 template <class T>
 void BubbleSort(T a[],int n ,bool cmp(T,T)){ 
 for(int i=0;i<n;i++){ 
 for(int j=0;j<n-i-1;j++){ 
 if(cmp(a[j],a[j+1]))Swap(a[j],a[j+1]);
 }
 }
 }
 
 int main(){ 
 int a[]={ 1,4,5,3,2,10,7,9,8,6};
 BubbleSort(a,10,cmp);
 for(int i=0;i<10;i++)printf("%d ",a[i]);
 }

# 选择排序(简单选择排序) #

## 选择排序介绍 ##

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每
    一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始
    位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序
    序列的末尾。以此类推，直到全部待排序的数据元素排完。

## 选择排序步骤： ##

从小到大进行排序
    
    1. 未排序序列中找到最小元素，存放到排序序列的起始位置。
    2. 从剩余未排序元素中继续寻找最小元素，然后放到已排序序列的末尾。
    3. 第二步，直到所有元素均排序完毕。

## c++源代码 ##

void SelectionSort(int a[],int n){ 
 for(int i=0;i<n-1;i++){ 
 int min_index=i;
 for(int j=i+1;j<n;j++){ 
 if(a[j]<a[min_index])min_index=j;
 }
 swap(a[min_index],a[i]);
 }
 }

# 插入排序 #

## 插入排序介绍 ##

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

## 直接插入排序步骤 ##

1. 从第一个元素开始，该元素可以认为已经被排序
    2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
    3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
    4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
    5. 将新元素插入到该位置后
    6. 重复步骤2~5

## c++源代码 ##

void InsertionSort(int a[],int n){ 
 for(int i=1;i<n;i++){ 
 int j=i,temp=a[i];
 while (j>0&&a[j-1]>temp)a[j]=a[j-1],j--;
 a[j]=temp;
 }
 }

# 归并排序 #

## 归并排序介绍 ##

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

## 归并排序步骤 ##

递归法:
    
    1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
    2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
    3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
    4. 重复步骤3直到某一指针到达序列尾
    5. 将另一序列剩下的所有元素直接复制到合并序列尾

迭代法:
    1. 将序列每相邻两个数字进行归并操作，形成ceil(n/2)个序列，排序后每个序列包含两/一个元素
    2. 若此时序列数不是1个则将上述序列再次归并，形成ceil(n/4)个序列，每个序列包含四/三个元素
    3. 重复步骤2，直到所有元素排序完毕，即序列数为1

## c++源代码 ##

void Merge( int list[], int sorted[], int n, int length ){ 
 int index=0;
 while (index+length<=n){ 
 int left=index+length,right=left+length,i=index,j=index+length;
 if(right>n)right=n;
 while (i<left&&j<right){ 
 if(list[i]>list[j])sorted[index++]=list[j++];
 else sorted[index++]=list[i++];
 }
 for(;i<left;i++)sorted[index++]=list[i];
 for(;j<right;j++)sorted[index++]=list[j];
 }
 }
 
 void MergeSort( int list[], int n )
 { 
 int * extra = new int [n];
 int length = 1; /* current length of sublist being merged */
 while( length < n ) { 
 Merge( list, extra, n, length ); 
 length *= 2;
 Merge( extra, list, n, length ); 
 length *= 2;
 }
 delete []extra;
 }

# 快速排序 #

## 快速排序介绍 ##

快速排序（Quicksort）是对冒泡排序的一种改进。它的基本思想是：通过一趟
    排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部
    分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个
    排序过程可以递归进行，以此达到整个数据变成有序序列。

## 快速排序步骤 ##

1. 挑选基准值：从数列中挑出一个元素，称为“基准”（pivot），
    2. 分割：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（与基准值相等的数可以到任何一边）。在这个分割结束之后，对基准值的排序就已经完成，
    3. 递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。

## c++ 源代码 ##

### 递归版 ###

#include <bits/stdc++.h>
 using namespace std;
 
 void quickSort(int a[], int leftEnd, int rightEnd)
 { 
 if (leftEnd >= rightEnd) return;
 int leftCursor = leftEnd, rightCursor = rightEnd + 1;
 int pivot = a[leftEnd];
 while (true)
 { 
 leftCursor++,rightCursor--;//每次循环双指针需移动一次
 while (a[leftCursor] < pivot) leftCursor++;
 while (a[rightCursor] > pivot) rightCursor--;
 if (leftCursor >= rightCursor) break;
 swap(a[leftCursor], a[rightCursor]);
 }
 a[leftEnd] = a[rightCursor];
 a[rightCursor] = pivot;
 quickSort(a, leftEnd, rightCursor - 1);
 quickSort(a, rightCursor + 1, rightEnd);
 }
 
 
 int main(){ 
 int n=10;
 int a[]={ 1,4,5,3,2,10,7,9,8,6};
 quickSort(a,0,n-1);
 for(int i=0;i<10;i++)printf("%d ",a[i]);
 }

### 非递归 ###

#include <bits/stdc++.h>
 using namespace std;
 
 template <class T>
 void quickSort(T a[], int n){ 
 	if (n <= 1) return;
 	int leftEnd, rightEnd;
 	int *StackA=new int[n],*StackB = new int [n],top=0;
 	StackA[top]=0;StackB[top]=n-1;top++;
 	while(top){ 
 		top--;leftEnd=StackA[top];rightEnd=StackB[top];
 		if (leftEnd >= rightEnd) continue;
 		int leftCursor = leftEnd, rightCursor = rightEnd + 1; 
 		T pivot = a[leftEnd];
 		while (true){ 
 			do{ leftCursor++;} while (a[leftCursor] < pivot);
 			do
 			{ rightCursor--;} while (a[rightCursor] > pivot);
 			if (leftCursor >= rightCursor) break; 
 			swap(a[leftCursor], a[rightCursor]);
 		}
 		a[leftEnd] = a[rightCursor];
 		a[rightCursor] = pivot;
 		StackA[top]=leftEnd;StackB[top]=rightCursor-1;top++;
 		StackA[top]=rightCursor+1;StackB[top]=rightEnd;top++;
 	}
 }
 
 
 int main(){ 
 int n=10;
 int a[]={ 1,4,5,3,2,10,7,9,8,6};
 quickSort(a,n);
 for(int i=0;i<10;i++)printf("%d ",a[i]);
 }

# 堆排序 #

## 堆排序介绍 ##

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

## 堆排序步骤 ##

大根堆：
    
    1.将长度为n的待排序的数组进行堆有序化构造成一个大顶堆
    2.将根节点与尾节点交换并输出此时的尾节点
    3.将剩余的n -1个节点重新进行堆有序化
    4.重复步骤2，步骤3直至构造成一个有序序列

## c++ 源代码 ##

#include <bits/stdc++.h>
 using namespace std;
 
 void adjust(int a[],int n){ 
 int t = 0;
 while(t<n) { 
 int j= 2*t+1;
 int r = j+1;
 if(a[t]<a[j]&&j<n&&a[j]>a[r])swap(a[t],a[j]),t=j;
 else if(a[t]<a[r]&&r<n)swap(a[t],a[r]),t=r;
 else break;
 }
 }
 
 void creatheap(int a[],int n){ 
 for(int i=n-1;i>0;i--){ 
 int t = i;
 while(t>0) { 
 int j = (t - 1) / 2;
 if (a[t] > a[j])swap(a[t], a[j]);
 else break;
 t = j;
 }
 }
 }//把一个数组调整一个大根堆
 
 
 void HeapSort(int a[], int n)
 { 
 creatheap(a,n);
 while (--n){ 
 swap(a[0],a[n]);
 adjust(a,n);
 }
 }
 int main(){ 
 int n=10;
 int a[]={ 1,4,5,3,2,10,7,9,8,6};
 HeapSort(a,n);
 for(int i=0;i<10;i++)printf("%d ",a[i]);
 }

# 计数排序 #

## 计数排序介绍 ##

计数排序（Counting sort）是一种稳定的线性时间排序算法。该计数排序使用
    一个额外的数组C ，其中第i个元素是待排序数组A中值等于i的元素的个数。然
    后根据数组C来将A中的元素排到正确的位置。

## 计数排序步骤 ##

1.  找出待排序的数组中最大和最小的元素
    2.  统计数组中每个值为i的元素出现的次数，存入数组C的第i项
    3.  对所有的计数累加（从C 中的第一个元素开始，每一项和前一项相加）
    4.  反向填充目标数组：将每个元素i放在新数组的第C[i]项，每放一个元素就将 C[i]减去1

# 桶排序 #

## 桶排序介绍 ##

桶排序（Bucket sort）是将数组分到有限数量的桶里。每个桶再个别排序（有
    可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）

## 桶排序步骤 ##

1. 设置一个定量的数组当作空桶子。
    2. 寻访序列，并且把项目一个一个放到对应的桶子去。
    3. 对每个不是空的桶子进行排序。
    4. 从不是空的桶子里把项目再放回原来的序列中。

# 基数排序 #

## 基数排序介绍 ##

基数排序（radix sort）属于“分配式排序”（distribution sort），又称
    “桶子法”（bucket sort）或bin sort，它是透过键值的部份资讯，将要排序
    的元素分配至某些“桶”中，藉以达到排序的作用

## 基数排序步骤 ##

1. 将所有待比较数值（正整数）统一为同样的数字长度，数字较短的数前面补零。
    2. 从最低位开始，依次进行一次排序。
    3. 从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。

# 排序方法分析 #

<table> 
 <thead> 
 <tr> 
 <th></th> 
 <th>冒泡排序</th> 
 <th>选择排序</th> 
 <th>插入排序</th> 
 <th>归并排序</th> 
 <th>快速排序</th> 
 <th>堆排序</th> 
 <th>计数排序</th> 
 <th>桶排序</th> 
 <th>基数排序</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td>最坏时间复杂度</td> 
 <td>O( n 2 n^2 n2)</td> 
 <td>O( n 2 n^2 n2)</td> 
 <td>O( n 2 n^2 n2)</td> 
 <td>O( n l o g n nlogn nlogn)</td> 
 <td>O( n 2 n^2 n2)</td> 
 <td>O( n l o g n nlogn nlogn)</td> 
 <td>O( n + k n+k n+k)</td> 
 <td></td> 
 <td>O(kn)</td> 
 </tr> 
 <tr> 
 <td>最优时间复杂度</td> 
 <td>O( n n n)</td> 
 <td>O( n 2 n^2 n2)</td> 
 <td>O( n n n)</td> 
 <td>O( n l o g n nlogn nlogn)</td> 
 <td>O( n l o g n nlogn nlogn)</td> 
 <td>O( n l o g n nlogn nlogn)</td> 
 <td>O( n + k n+k n+k)</td> 
 <td>O(n)</td> 
 <td>O(kn)</td> 
 </tr> 
 <tr> 
 <td>平均时间复杂度</td> 
 <td>O( n 2 n^2 n2)</td> 
 <td>O( n 2 n^2 n2)</td> 
 <td>O( n 2 n^2 n2)</td> 
 <td>O( n l o g n nlogn nlogn)</td> 
 <td>O( n l o g n nlogn nlogn)</td> 
 <td>O( n l o g n nlogn nlogn)</td> 
 <td>O( n + k n+k n+k)</td> 
 <td>O(n)</td> 
 <td>O(kn)</td> 
 </tr> 
 <tr> 
 <td>辅助空间</td> 
 <td>O( 1 1 1)</td> 
 <td>O( 1 1 1)</td> 
 <td>O( 1 1 1)</td> 
 <td>O( n n n)</td> 
 <td>O( l o g n logn logn)</td> 
 <td>O( 1 1 1)</td> 
 <td>O( n + k n+k n+k)</td> 
 <td>O( n + b n n+bn n+bn)</td> 
 <td>O( n + k n+k n+k)</td> 
 </tr> 
 <tr> 
 <td>稳定性</td> 
 <td>稳定</td> 
 <td>不稳定</td> 
 <td>稳定</td> 
 <td>稳定</td> 
 <td>不稳定</td> 
 <td>不稳定</td> 
 <td>稳定</td> 
 <td>稳定</td> 
 <td>稳定</td> 
 </tr> 
 </tbody> 
</table>