六安网站建设培训,制作网站需要多少时间,wordpress如何恢复默认主题,360搜索引擎的特点快速排序介绍
快速排序是一种经典高效的排序方法#xff0c;是分治策略在排序上的具体体现。将一个大的待排序列分割成若干个小的有序序列#xff0c;最终将各个小的有序序列合并成一个大的有序序列。
快速排序的实现原理
选择一个基准值#xff0c;将小于基准值的元素放…快速排序介绍
快速排序是一种经典高效的排序方法是分治策略在排序上的具体体现。将一个大的待排序列分割成若干个小的有序序列最终将各个小的有序序列合并成一个大的有序序列。
快速排序的实现原理
选择一个基准值将小于基准值的元素放在基准值左侧大于基准值的元素放在基准值右侧基准值放在中间。基准值可以选择待排序列的第一个元素最后一个元素中间元素也可以选择三者的中位数提高快排效率。一轮快速排序后基准值已经有序之后对基准值两侧的数据分别进行快排这是一个递归的过程最终整个序列有序。整个过程类似于树的前序遍历每一轮的过程使用双指针所以快排本质上是树的前序遍历双指针。
快速排序的具体实现
基准值选择不同代码实现不同但本质上都是树的前序遍历双指针
选择第一个元素作为基准值代码实现
代码实现
public void quickSort(int[] array, int left, int right) {if (left right) {int pivot array[left];int i right 1;for (int j right; j left; j--) {if (array[j] pivot) {i--;int temp array[i];array[i] array[j];array[j] temp;}}int pivotIndex i - 1;int temp array[pivotIndex];array[pivotIndex] array[left];array[left] temp;quickSort(array, left, pivotIndex - 1);quickSort(array, pivotIndex 1, right);}
}选择最后一个元素作为基准值代码实现
代码实现
public void quickSort(int[] array, int left, int right) {if (left right) {int pivot array[right];int i left - 1;for (int j left; j right; j) {if (array[j] pivot) {i;int temp array[i];array[i] array[j];array[j] temp;}}int pivotIndex i 1;int temp array[pivotIndex];array[pivotIndex] array[right];array[right] temp;quickSort(array, left, pivotIndex - 1);quickSort(array, pivotIndex 1, right);}
}选择中值作为基准值代码实现
代码实现
public static void quickSort(int[] array, int start, int end) {if (start end) {return;}int left start;int right end;int mid (left right) / 2;int pivot array[mid];while (left right) {while (left right array[left] pivot) {left;}while (left right array[right] pivot) {right--;}if (left right) {int temp array[left];array[left] array[right];array[right] temp;left;right--;}}quickSort(array, start, right);quickSort(array, left, end);
}快速排序复杂度分析
时间复杂度
平均情况下O(n log n)。在平均情况下快速排序通常具有优秀的性能。每次分割都将数组分为两部分每部分的大小约为原数组的一半。因此在进行 log n 次递归后每个子数组都会被完全排序总的时间复杂度是 O(n log n)。
最坏情况下O(n^2)。最坏情况发生在选择基准值不平衡的情况下导致每次分割只能减少一个元素。例如如果数组已经有序或接近有序且始终选择第一个元素作为基准值那么就会出现最坏情况。为了避免最坏情况可以使用随机选择基准值或者三数取中法等策略。
最好情况下O(n )。最好情况发生在数组有序
空间复杂度
快速排序是一种原地排序算法不需要额外的内存空间因此其空间复杂度是 O(1)。
稳定性
快速排序是不稳定的排序算法即相等元素的相对顺序可能在排序后改变。
