软件公司网站素材,石家庄长安区网站建设公司,WordPress离线编写,采购平台排名快速排序#xff08;Quick Sort#xff09;也是一种典型的交换排序算法#xff0c;通过交换数据元素的位置进行排序。 一、算法基本思想 #xff08;1#xff09;基本思想 快速排序的基本思想就是#xff1a;通过一趟排序将要排序的数据分割成独立的两部分#xff0c;其… 快速排序Quick Sort也是一种典型的交换排序算法通过交换数据元素的位置进行排序。 一、算法基本思想 1基本思想 快速排序的基本思想就是通过一趟排序将要排序的数据分割成独立的两部分其中一部分的所有数据都比另外一部分的所有数据都要小然后再按此方法对这两部分数据分别进行快速排序整个排序过程可以递归进行以此达到整个数据变成有序序列。快速排序采用了分治法来解决问题。 2运行过程 快速排序算法的运行过程如下 1、从序列中挑出一个元素称为“基准”pivot。一般是选取序列的第一个元素。 2、重新排序数列所有比基准值小的元素摆放在基准前面所有比基准值大的元素摆在基准的后面相同的数可以到任一边。在这个分区结束之后该基准就处于数列的中间位置。这个称为分区partition操作。 3、递归地recursive把小于基准值元素的子数列和大于基准值元素的子数列排序。 4、直到序列的大小是0或1也就是所有元素都已经被排序好了递归结束。 3示例 1、一次快速排序过程 所有比基准值小的元素摆放在基准前面所有比基准值大的元素摆在基准的后面最后找到基准元素的位置。 2、整个快速排序过程 二、算法实现核心代码 C实现 void swap(int *x, int *y) {int t *x;*x *y;*y t;
}
void quick_sort_recursive(int arr[], int start, int end) {if (start end)return;int mid arr[end];int left start, right end - 1;while (left right) {while (arr[left] mid left right)left;while (arr[right] mid left right)right--;swap(arr[left], arr[right]);}if (arr[left] arr[end])swap(arr[left], arr[end]);elseleft;quick_sort_recursive(arr, start, left - 1);quick_sort_recursive(arr, left 1, end);
}
void quick_sort(int arr[], int len) {quick_sort_recursive(arr, 0, len - 1);
} Java实现 class quick_sort {int[] arr;private void swap(int x, int y) {int temp arr[x];arr[x] arr[y];arr[y] temp;}private void quick_sort_recursive(int start, int end) {if (start end)return;int mid arr[end];int left start, right end - 1;while (left right) {while (arr[left] mid left right)left;while (arr[right] mid left right)right--;swap(left, right);}if (arr[left] arr[end])swap(left, end);elseleft;quick_sort_recursive(start, left - 1);quick_sort_recursive(left 1, end);}public void sort(int[] arrin) {arr arrin;quick_sort_recursive(0, arr.length - 1);}
} 三、算法改进和变种 对于快速排序改进的方法可以参考《大话数据结构这本书》。快速排序的优点在于对于大量数据的时候很容易将某个元素放到对应的位置。而快速排序的缺点也很明显 一是如果原始数据就是有序的那么快速排序过程中对序列的划分就十分不均匀将序列分为了1和n-1的大小而通常希望的最理想状态是二分 二是对于小数组进行排序时也需要递归进行几次才能将数据放到正确的位置 三是排序快速是不稳定的当重复数据很多时效率比较低。 针对快速排序的缺点对于快速排序主要有以下三个改进方案 1优化选取基准pivotkey — — 三数取中法 三数取中法的思想如下选取序列左端、中间和右端三个数据元素按大小进行排序选择中间大小的元素作为基准。 2序列较小时使用插入排序代替快速排序 在递归过程当排序的子序列小于预定的值M时采用插入插入排序。 3重复元素较多使用三分区法 通过划分让相等的元素连续地摆放然后只对左侧小于V的序列和右侧大于V对的序列进行排序。 如上图 从左至右扫描数组维护一个指针lt使得[lo…lt-1]中的元素都比v小一个指针gt使得所有[gt1….hi]的元素都大于v以及一个指针i使得所有[lt…i-1]的元素都和v相等。元素[i…gt]之间是还没有处理到的元素i从lo开始从左至右开始扫描 1、如果a[i]v:交换a[lt]和a[i]lt和i自增 2、如果a[i]v交换a[i]和a[gt],gt自减 3、如果a[i]vi自增。 四、算法性能时间复杂度、空间复杂度、稳定性分析 快速排序是通常被认为在同数量级O(nlog2n)的排序方法中平均性能最好的。 但若初始序列按关键字有序或基本有序时快排序反而蜕化为冒泡排序也就是说快速排序最坏情况下时间复杂度为O(n^2)空间复杂度为O(n)。 如果每次排序时所选的基准都能讲序列进行二分那么此时的快速排序效果最好也就是说快速排序在最好情况下的时间复杂度为O(nlogn)空间复杂度为O(logn)。 快速排序的平均时间复杂度为O(nlogn)空间复杂度为O(logn)。快速排序是一种不稳定的排序算法。 参考文献 1、浅谈算法和数据结构: 四 快速排序 http://www.cnblogs.com/yangecnu/p/Introduce-Quick-Sort.html 2、快速排序算法及其改进算法实现 http://blog.csdn.net/lsjseu/article/details/9749587 3、快速排序及改进 http://flyingdutchman.iteye.com/blog/1863691 4、快速排序2算法改进--小的子文件、三者取中、重复关键字三路划分序及改进 https://www.zybuluo.com/quinn/note/78606 5、怎样让快速排序最快 http://blog.sina.com.cn/s/blog_4dff8712010136jh.html
