常见的10种排序算法与C#实现
2020-10-13 本文已影响0人
雄关漫道从头越
一、算法分类
常见算法可以分为两大类：
1.非线性时间比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此称为非线性时间比较类排序。
2.线性时间非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。
算法分类
二、算法复杂度
算法复杂度
三、效率比较
以下是5万条0-1000000随机数据，不同算法的耗时比较：
算法效率比较
四、算法实现
1.冒泡排序
核心思想：内外两层循环，外层是需要循环的次数，内层循环两两比较相邻两个元素的大小，出现逆序交换位置，小的往左（前），大的往右（后），循环结束得到有序序列，因该过程类似冒泡，所以叫冒泡排序
时间复杂度：O(n^2)
算法稳定
冒泡排序
代码：
/// <summary>
/// 冒泡排序，算法的时间复杂度为O(n^2)，算法稳定
/// </summary>
/// <param name="arr"></param>
public static void Sort(int[] arr)
{
int length = arr.Length;
for (int i = 0; i < length; i++)//外层循环
{
for (int j = 0; j < length - i - 1; j++)//内层循环
{
if (arr[j] > arr[j + 1]) //前后比较，交换顺序，大的往后移，小的往前移
{
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
2.选择排序
核心思想：内外两层循环，外层是需要循环的次数，内层循环从待排序的数据元素中选出最小（最大）的元素，存放到序列的起始位置，直到全部待排序的数据元素排完
时间复杂度：O(n^2)
算法不稳定
选择排序
代码：
/// <summary>
/// 选择排序，算法的时间复杂度为O(n^2)，算法不稳定
/// </summary>
/// <param name="arr"></param>
public static void Sort(int[] arr)
{
int length = arr.Length;
int min = 0; // 指向最小的元素的位置
for (int i = 0; i < length - 1; i++)// 外层循环
{
min = i;
for (int j = i + 1; j < length; j++)// 内存循环
{
if (arr[min] > arr[j])
{
min = j;//保存最小位置
}
}
if (min != i)
{
int temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;
}
}
}
3.插入排序
核心思想：插入排序的基本思想就是将无序序列插入到有序序列中
时间复杂度：O(n ^2)，最好O(n)，最坏O(n ^2)
算法稳定
插入排序
代码：
/// <summary>
/// 插入排序，算法的时间复杂度为O(n^2)，算法稳定
/// 升序排序
/// </summary>
/// <param name="arr"></param>
public static void Sort(int[] arr)
{
int length = arr.Length;
int temp = 0;//保存基准数
int index = 0;//坑的位置
for (int i = 1; i < length; i++)//外层遍历无序序列
{
index = i;
temp = arr[i];
for (int j = i - 1; j >= 0; j--) //内层遍历有序序列(从后往前)
{
if (temp < arr[j])//基准数根有序序列中的元素比较
{
arr[j + 1] = arr[j];
index = j;
}
}
arr[index] = temp;//填坑
}
}
4.希尔排序
核心思想：希尔排序是插入排序的一种高效率的实现，也叫缩小增量排序。先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录基本有序时再对全体记录进行一次直接插入排序。
时间复杂度：O(n ^1.3)，最好O(n)，最坏O(n ^2)
算法不稳定
希尔排序
代码：
/// <summary>
/// 希尔排序，算法的时间复杂度为O(n^1.3)，最好O(n)，最坏O(n^2)，算法不稳定
/// </summary>
/// <param name="arr"></param>
public static void Sort(int[] arr)
{
int length = arr.Length;
int gap = length;//步长
while (gap > 1)
{
gap = gap / 3 + 1;// 步长递减公式
for (int i = 0; i < gap; i++)//分组, 对每一组, 进行插入排序
{
int temp = 0;//保存基准数
int index = 0;//坑的位置
for (int j = i + gap; j < length; j += gap)
{
index = j;
temp = arr[j];
for (int k = j - gap; k >= 0; k -= gap)//有序序列(从后往前遍历)
{
if (temp < arr[k])//基准数根有序序列中的元素比较
{
arr[k + gap] = arr[k];
index = k;
}
else
{
break;
}
}
arr[index] = temp;//填坑
}
}
}
}
5.快速排序
核心思想：
1.先从数列中取出一个数作为基准数。
2.分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3.再对左右区间重复第1步，直到各区间只有一个数。
时间复杂度：O(nlogn)，最好O(nlogn)，最坏O(n^2)
算法不稳定
快速排序
代码：
/// <summary>
/// 快速排序，算法的时间复杂度为O(nlogn)，算法不稳定
/// 挖坑排序+分治算法
/// </summary>
/// <param name="arr"></param>
/// <returns></returns>
public static void Sort(int[] arr, int low, int high)
{
if (low < high)
{
int l = low, r = high;
int k = arr[l];//比较基数
while (l < r)
{
while (l < r && arr[r] >= k)//从右往左查找第一个小于基数k的数，并放到左边
r--;
if (l < r)
arr[l++] = arr[r];//将arr[r]填到arr[l]中，arr[r]就形成了一个新的坑，进行过一次替换后，没必要将替换后的两值再次比较，所以l++直接下一位与k对比
while (l < r && arr[l] < k)//从左往右查找第一个大于基数k的数，并放到右边
l++;
if (l < r)
arr[r--] = arr[l];//将arr[l]填到arr[r]中，arr[l]就形成了一个新的坑，进行过一次替换后，没必要将替换后的两值再次比较，所以r--直接上一位与k对比
}
//退出时，l等于r。将k填到这个坑中。
arr[l] = k;
Sort(arr, low, l - 1);
Sort(arr, l + 1, high);
}
}
6.归并排序
核心思想：归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。
时间复杂度：O(nlogn)，最好O(nlogn)，最坏O(nlogn)
算法稳定
归并排序
归并排序-分治
代码：
/// <summary>
/// 归并排序，算法的时间复杂度为O(nlogn)，算法稳定
/// </summary>
/// <param name="arr"></param>
/// <returns></returns>
public static void Sort(int[] arr)
{
int length = arr.Length;
int[] temp = new int[length];//在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
Sort(arr, 0, length - 1, temp);
}
/// <summary>
/// 归并排序，算法的时间复杂度为O(nlogn)，算法稳定
/// </summary>
/// <param name="arr"></param>
/// <param name="low"></param>
/// <param name="high"></param>
public static void Sort(int[] arr, int low, int high, int[] temp)
{
int mid = (low + high) / 2;
if (low < high)
{
Sort(arr, low, mid, temp);//左边归并排序，使得左子序列有序
Sort(arr, mid + 1, high, temp);//右边归并排序，使得右子序列有序
Merge(arr, low, mid, high, temp);//将两个有序子数组合并操作
}
}
private static void Merge(int[] arr, int low, int mid, int high, int[] temp)
{
int i = low;//左指针
int j = mid + 1;//右指针
int k = 0;//临时数组指针
//把较小的数先移到新数组中
while (i <= mid && j <= high)
{
//从两个数组中取出最小的放入临时数组
if (arr[i] < arr[j])
{
temp[k++] = arr[i++];
}
else
{
temp[k++] = arr[j++];
}
}
//两个数组之一可能存在剩余的元素
//把左边剩余的移入新数组
while (i <= mid)
{
temp[k++] = arr[i++];
}
//把右边剩余的移入新数组
while (j <= high)
{
temp[k++] = arr[j++];
}
k = 0;
//将temp中的元素全部拷贝到原数组中
while (low <= high)
{
arr[low++] = temp[k++];
}
}
7.堆排序
核心思想：
a.将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;
b.将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;
c.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。
时间复杂度：O(nlogn)，最好O(nlogn)，最坏O(nlogn)
算法不稳定
堆排序
代码：
/// <summary>
/// 堆排序，算法的时间复杂度为O(nlogn)，算法不稳定
/// </summary>
/// <param name="arr"></param>
/// <returns></returns>
public static void Sort(int[] arr)
{
int length = arr.Length;
//1.构建大顶堆
for (int i = length / 2 - 1; i >= 0; i--)
{
//从第一个非叶子结点从下至上，从右至左调整结构
AdjustHeap(arr, i, length);
}
//2.调整堆结构+交换堆顶元素与末尾元素
for (int j = length - 1; j > 0; j--)
{
//将堆顶元素与末尾元素进行交换
int temp = arr[0];
arr[0] = arr[j];
arr[j] = temp;
AdjustHeap(arr, 0, j);//重新对堆进行调整
}
}
//调整大顶堆（仅是调整过程，建立在大顶堆已构建的基础上）
public static 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值放到最终的位置
}
8.计数排序
核心思想：
a.找出待排序的数组中最大和最小的元素；
b.统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
c.对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
d.反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。
时间复杂度：O(n+k)，最好O(n+k)，最坏O(n+k)，k为元素最大值
算法稳定
计数排序
代码：
/// <summary>
/// 计数排序，算法的时间复杂度为O(n+k)，算法稳定
/// k为最大值
/// </summary>
/// <param name="arr"></param>
public static void Sort(int[] arr)
{
int length = arr.Length;
//一：求取最大值和最小值，计算中间数组的长度：中间数组是用来记录原始数据中每个值出现的频率
int max = arr[0], min = arr[0];
for (int i = 0; i < length; i++)
{
if (arr[i] > max)
{
max = arr[i];
}
if (arr[i] < min)
{
min = arr[i];
}
}
//二：有了最大值和最小值能够确定中间数组的长度
//存储5-0+1 = 6
int[] pxA = new int[max - min + 1];
//三.循环遍历旧数组计数排序: 就是统计原始数组值出现的频率到中间数组pxA中
for (int i = 0; i < length; i++)
{
pxA[arr[i] - min] += 1;//数的位置上+1
}
//四.遍历输出
//创建最终数组，就是返回的数组，和原始数组长度相等，但是排序完成的
int[] result = new int[length];
int index = 0;//记录最终数组的下标
//先循环每一个元素 在计数排序器的下标中
for (int i = 0; i < pxA.Length; i++)
{
//循环出现的次数
for (int j = 0; j < pxA[i]; j++)
{//pxA[i]:这个数出现的频率
result[index++] = i + min;//因为原来减少了min现在加上min，值就变成了原来的值
}
}
Array.Copy(result, arr, length);
}
9.桶排序
核心思想：桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。
a.设置一个定量的数组当作空桶；
b.遍历输入数据，并且把数据一个一个放到对应的桶里去；
c.对每个不是空的桶进行排序；
d.从不是空的桶里把排好序的数据拼接起来。
时间复杂度：O(n+k)，最好O(n)，最坏O(n^2)
算法稳定
桶排序
代码：
/// <summary>
/// 桶排序，算法的时间复杂度为O(n+k)，算法稳定
/// </summary>
/// <param name="arr"></param>
public static void Sort(int[] arr)
{
int length = arr.Length;
// 计算最大值与最小值
int max = int.MinValue;
int min = int.MaxValue;
for (int i = 0; i < length; i++)
{
max = Math.Max(max, arr[i]);
min = Math.Min(min, arr[i]);
}
// 计算桶的数量
int bucketNum = (max - min) / length + 1;
List<List<int>> bucketArr = new List<List<int>>(bucketNum);
for (int i = 0; i < bucketNum; i++)
{
bucketArr.Add(new List<int>());
}
// 将每个元素放入桶
for (int i = 0; i < length; i++)
{
int num = (arr[i] - min) / (length);
bucketArr[num].Add(arr[i]);
}
// 对每个桶进行排序
for (int i = 0; i < bucketArr.Count; i++)
{
bucketArr[i].Sort();
}
// 将桶中的元素赋值到原序列
int index = 0;
for (int i = 0; i < bucketArr.Count; i++)
{
for (int j = 0; j < bucketArr[i].Count; j++)
{
arr[index++] = bucketArr[i][j];
}
}
}
10.基数排序
核心思想：基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。
a.取得数组中的最大数，并取得位数；
b.arr为原始数组，从最低位开始取每个位组成radix数组；
c.对radix进行计数排序（利用计数排序适用于小范围数的特点）；
时间复杂度：O(n * k)，最好O(n * k)，最坏O(n * k)
算法稳定
基数排序
代码：
/// <summary>
/// 基数排序，算法的时间复杂度为O(n*k)，算法稳定
/// </summary>
/// <param name="arr"></param>
public static void Sort(int[] arr)
{
int length = arr.Length;
//待排序列最大值
int max = arr[0];
int exp;//指数
//计算最大值
for (int i = 0; i < length; i++)
{
if (arr[i] > max)
{
max = arr[i];
}
}
//从个位开始，对数组进行排序
for (exp = 1; max / exp > 0; exp *= 10)
{
//存储待排元素的临时数组
int[] temp = new int[length];
//分桶个数
int[] buckets = new int[10];
//将数据出现的次数存储在buckets中
for (int i = 0; i < length; i++)
{
//(value / exp) % 10 :value的最底位(个位)
buckets[(arr[i] / exp) % 10]++;
}
//更改buckets[i]，
for (int i = 1; i < 10; i++)
{
buckets[i] += buckets[i - 1];
}
//将数据存储到临时数组temp中
for (int i = length - 1; i >= 0; i--)
{
temp[buckets[(arr[i] / exp) % 10] - 1] = arr[i];
buckets[(arr[i] / exp) % 10]--;
}
//将有序元素temp赋给arr
Array.Copy(temp, 0, arr, 0, length);
}
}
