快速排序

算法介绍

快速排序是对冒泡排序的一种优化，是一种采用了分治思想的交换排序。具体思想如下： 1、将数组第一个位置的数作为基准，使用双指针指向数组的两端，然后向中间扫描(注意：先从右往左扫描，这样两指针相遇的位置将是从右开始第一个小于基准的数，可以直接与基准交换)。 2、在从右往左的扫描中，如果发现有比基准小的数就停下来。 3、在从左往右的扫描中，如果发现有比基准大的数就停下来。 4、交换这两个数。 5、重复上述过程直到两指针相遇。 6、将两指针相遇的数与数列第一位的基准交换。（此时将固定基准在这个数组最终的位置，因为左侧的数都比它小，右侧的数都比它大） 7、将基准两侧的数划为两个区分别进行上述计算

代码

void quick_sort(int[] array, int left, int right){ if(left >= right) return; int i = left, j = right; while(i < j){ while( j > i && array[j] >= array[left]) j--; while( i < j && array[i] <= array[left]) i++; swap(array,i,j); } swap(array,left,j); quick_sort(array, left, j - 1); quick_sort(array, j + 1, right); } static void swap(int[] array, int i, int j){ int temp = array[i]; array[i] = array[j]; array[j] = temp; }

性能分析

平均时间复杂度O(nlogn)，最坏时间复杂度为O(n^2)(每次划分只得到一个比上一次划分少一个记录的子序列,可以得到一个斜着的n层二叉树) 空间复杂度涉及到递归对栈的调用，为O(logn） 快速排序为不稳定排序

四级标题

五级标题

六级标题