快速排序

要点

时间复杂度–平均情况：O(nlogn)；最好情况：O(nlogn)；最坏情况O(n²)。辅助空间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; } } }