快速排序

xiaoxiao2021-03-01  16

要点

时间复杂度–平均情况:O(nlogn);最好情况:O(nlogn);最坏情况O(n2)。辅助空间O(logn)~O(n)。快速排序是一种不稳定的排序方式。快排的基本思想:定义一个基准值将待排记录分割为独立的两部分,其中一部记录的关键字均比另一部分的关键字小,再分别对这两部分记录继续进行排序,直到每部分记录只有一个关键字。每一趟排序都只能确定基准值的位置。方式二的交换次数只有方式一的1/2。快速排序的优化: 优化选取基准值:三数取中,九数取中…优化不必要的交换(采用替换而不是交换的方式)优化递归操作优化小数组时的排序方案:如果数组非常小,其实快速排序反而不如直接插入排序来得更好(直接插入排序是简单排序中性能最好的)。其原因在于快速排序用到了递归操作。当数组长度不大于X(有认为X=7比较合适,也有认为50更合理,实际应用可适当调整),就用直接插入排序,这样就能保证最大化地利用两种排序的优势来完成排序工作。

基本思路(一趟排序)

方式一: 定义一个基准值(分界值)-- 数组开始位置为基准值定义两个指针start和end分别指向数组两端end指针向前遍历(从右往左)直到找到一个比基准值小的关键字(或与start指针相遇),则基准值和当前end指针指向的关键字交换位置,交换后当前end指向基准值start指针向后遍历(从左往右)直到找到一个比基准值大的关键字(或与end指针相遇),则基准值和当前start指针指向的关键字交换位置,交换后当前start指向基准值重复步骤3和步骤4,若出现start指针和end指针相遇的情形(start==end),则返回基准值所在位置(start或end),此时排序完成。基准值已将待排记录分割为独立的两部分,其中一部记录的关键字均比另一部分的关键字小。 public int sort(int[] nums, int start, int end) { int base = nums[start]; // 基准值 while (start < end) { // end指针向前扫描 while (start < end && nums[end] >= base) end--; // 出现小于基准值的关键字,交换 swap(nums, start, end); // start指针向后扫描 while (start < end && nums[start] <= base) start++; // 出现大于基准值的关键字,交换 swap(nums, start, end); } // 返回相遇位置,即确定好的基准值的位置 return start; } 方式二: 定义一个基准值(分界值)-- 数组开始位置为基准值定义两个指针start和end分别指向数组两端end指针向前遍历(从右往左)直到找到一个比基准值小的关键字(或与start指针相遇)start指针向后遍历(从左往右)直到找到一个比基准值大的关键字(或与end指针相遇)交换start指针和end指针指向的关键字重复步骤3、步骤4和步骤5,若出现start指针和end指针相遇的情形,则start/end指针指向的关键字与基准值(数组开始位置)进行交换并返回交换后基准值的位置(start或end),完成这次排序。基准值已将待排记录分割为独立的两部分,其中一部记录的关键字均比另一部分的关键字小。 public int sort(int[] nums, int start, int end) { // base为基准值,baseKey记录基准值的位置 int base = nums[start], baseKey = start; while (start < end) { // end指针向前扫描,直到出现小于基准值的关键字 while (start < end && nums[end] >= base) end--; // start指针向后扫描,直到出现大于基准值的关键字 while (start < end && nums[start] <= base) start++; // 判断start指针和end指针的关系, // 从而确定是交换start和end指针指向的关键字,还是交换基准值和start/end指针指向的关键字 if (start < end) { swap(nums, start, end); } else { swap(nums, baseKey, end); } } // 返回相遇位置,即确定好的基准值的位置 return start; }

实现快速排序

public void quickSort(int[] nums, int start, int end) { int baseKey; // 上次排序后基准值的位置 if (start < end) { baseKey = sort(nums, start, end); // 获取已确定位置的基准值的位置 quickSort(nums, start, baseKey - 1); // 对在基准值的左半部分进行排序 quickSort(nums, baseKey + 1, end); // 对在基准值的右半部分进行排序 } }
补充:交换方法
public void swap(int[] nums, int a, int b) { int temp; temp = nums[a]; nums[a] = nums[b]; nums[b] = temp; }

快速排序优化

public class QuickSort { // 尾递归优化 public void quickSort(int[] nums, int start, int end) { int baseKey; // 基准值的位置 if ((end - start) > MAX_LENGTH_INSERT_SORT) { while (start < end) { baseKey = sort(nums, start, end); // 将待排记录一分为二 quickSort(nums, start, baseKey - 1); // 对左半部分待排记录递归排序 start = baseKey + 1; // 尾递归 } } else { // 直接插入排序 insertSort(nums); } } // 一趟排序优化:三数取中, 采用替换方式 public int sort(int[] nums, int start, int end) { int base; // 定义基准值 int mid = (start + end) / 2; // 中间元素的下标 // 找出三个数中的中间值并且将它置于待排记录的开始位置 if (nums[start] > nums[end]) swap(nums, start, end); if (nums[mid] > nums[end]) swap(nums, mid, end); if (nums[mid] > nums[start]) swap(nums, start, mid); // 为基准值赋值,为处理后待排记录的开始位置的关键字的值 base = nums[start]; while (start < end) { while (start < end && nums[end] >= base) end--; // 采用替换而不是交换的方式进行操作 nums[start] = nums[end]; while (start < end && nums[start] <= base) start++; // 采用替换而不是交换的方式进行操作 nums[end] = nums[start]; } nums[start] = base; // 将确定好位置的关键字替换回基准值 return start; } // 交换 public void swap(int[] nums, int a, int b) { int temp; temp = nums[a]; nums[a] = nums[b]; nums[b] = temp; } }
补充:直接插入排序[了解一下]
public void insertSort(int[] nums) { int guard, i, j; for (i = 1; i < nums.length; i++) { if (nums[i] < nums[i - 1]) { guard = nums[i]; for (j = i - 1; j >= 0 && nums[j] > guard; j--) nums[j + 1] = nums[j]; nums[j + 1] = guard; } } }
转载请注明原文地址: https://www.6miu.com/read-3100114.html

最新回复(0)