西安推荐企业网站制作平台,软装设计方案ppt,手机软件定制开发,网络营销师怎么考文章目录 前言快速排序算法1、概念与实现2、优化 前言
算法是程序员的基础能力之一#xff0c;资质越老的程序员在这方面理解会越深#xff0c;很多时候项目在某个需要优化、提升的节点时#xff0c;往往一些算法的使用就可以大大提升程序性能。当然#xff0c;对于不同项… 文章目录 前言快速排序算法1、概念与实现2、优化 前言
算法是程序员的基础能力之一资质越老的程序员在这方面理解会越深很多时候项目在某个需要优化、提升的节点时往往一些算法的使用就可以大大提升程序性能。当然对于不同项目需求要用适合的算法在效率与业务之间寻找平衡。 此为第一章快排算法。 快速排序算法
1、概念与实现
平均时间复杂度为O(n log n)最坏的情况是On ^ 2。但综合的看比许多其他简单的排序算法如插入排序和选择排序的O(n²)更高效所以使用面也更广。 排序分为几步 1、选取一个基准元素 2、把比她小的移到左侧大的移到右侧 3、对两侧的元素进行递归筛选然后再对两侧的元素执行第一步操作 我们从中能分析出最坏的结果就是每次都选择最小的元素和最大的元素示例代码我就使用AI生成了毕竟网上一搜就有。
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
/*
代码分析
QuickSort方法:
递归地对数组进行排序。首先通过Partition方法将数组划分然后对划分后的子数组进行排序。Partition方法:
选择数组的最后一个元素作为枢轴pivot。
将所有小于枢轴的元素移动到枢轴的左边大于枢轴的元素移动到右边。
返回枢轴的位置。Swap方法:
交换数组中两个元素的位置。ArrayToString方法:
将数组转换为字符串格式以便在控制台中打印。
*/
public class QuickSortExample : MonoBehaviour
{void Start(){int[] array { 34, 7, 23, 32, 5, 62 };Debug.Log(Unsorted Array: ArrayToString(array));QuickSort(array, 0, array.Length - 1);Debug.Log(Sorted Array: ArrayToString(array));}void QuickSort(int[] array, int low, int high){if (low high){int pi Partition(array, low, high);QuickSort(array, low, pi - 1);QuickSort(array, pi 1, high);}}int Partition(int[] array, int low, int high){int pivot array[high];int i (low - 1);for (int j low; j high; j){if (array[j] pivot){i;Swap(ref array[i], ref array[j]);}}Swap(ref array[i 1], ref array[high]);return (i 1);}void Swap(ref int a, ref int b){int temp a;a b;b temp;}string ArrayToString(int[] array){return string.Join(, , array);}
}
2、优化
1随机选取中轴数 在快速排序算法中选取哪个元素作为枢轴pivot是至关重要的因为这会直接影响到算法的排序效率。如果选取的枢轴不是数组中间位置的数字而是偏向于较小或较大的数字排序速度就会受到影响。如果选取的枢轴恰好是最大或最小的数字情况将更糟因为这样会导致左侧或右侧没有元素可排序相当于每次遍历只完成了一个元素的排序。由于确定确切的中位数需要耗费大量的计算资源因此我们只能通过随机选择元素来降低出现最坏情况的概率。虽然随机选择旨在减少选取最大值和最小值的概率但实际上随机选择可能会选取到不理想的枢轴元素。因此尽管随机选择能够一定程度上降低最坏情况的发生概率但对于排序来说随机选择并没有提供太大的帮助。 通过随机选择枢轴可以减少最坏情况发生的概率
void QuickSort(int[] array, int low, int high)
{if (low high){int pi RandomizedPartition(array, low, high);QuickSort(array, low, pi - 1);QuickSort(array, pi 1, high);}
}int RandomizedPartition(int[] array, int low, int high)
{int pivotIndex Random.Range(low, high 1);Swap(ref array[pivotIndex], ref array[high]);return Partition(array, low, high);
}
2三向切分 既然知道原理我们其实也能猜到如果中轴数更接近中位数效率会大幅提升。为了确保选择的中轴数更接近于中位数可以采取一种策略在排序之前首先对数组的头部、中部和尾部的三个元素进行排序将最小的数字放在头部中间的数字放在中部最大的数字放在尾部。然后用3个数字去提高有效接近中位数的中轴元素。 三向切分将数组分为三部分小于枢轴的部分、等于枢轴的部分和大于枢轴的部分适用于大量重复元素的情况
void QuickSort3Way(int[] array, int low, int high)
{if (low high){int lt low, i low 1, gt high;int pivot array[low];while (i gt){if (array[i] pivot)Swap(ref array[lt], ref array[i]);else if (array[i] pivot)Swap(ref array[i], ref array[gt--]);elsei;}QuickSort3Way(array, low, lt - 1);QuickSort3Way(array, gt 1, high);}
}
3小区间使用插入排序 排序算法有各自的使用量级当量级不同时排序效率可能不一样。以插入排序为例它对列表的有序程度和元素数量都十分敏感。当列表几乎有序时插入排序表现最佳因为它只需要简单地比较少量元素并执行少量交换操作。相反如果列表几乎是逆序的插入排序的性能将急剧下降因为它需要大量的比较和交换操作来将每个元素移动到正确的位置。 在小数组如小于10个元素时插入排序比快速排序更高效。可以设置一个阈值当子数组小于该阈值时使用插入排序
void QuickSort(int[] array, int low, int high)
{const int CUTOFF 10;if (high low CUTOFF - 1){InsertionSort(array, low, high);return;}if (low high){int pi RandomizedPartition(array, low, high);QuickSort(array, low, pi - 1);QuickSort(array, pi 1, high);}
}void InsertionSort(int[] array, int low, int high)
{for (int i low; i high; i){for (int j i; j low array[j] array[j - 1]; j--){Swap(ref array[j], ref array[j - 1]);}}
}
