北京专业网站改版,学网站制作,凡科的模板做网站,手机网站移动应用快速排序 1.快速排序原理 快速排序是一种应用很广泛的排序算法#xff0c;与归并排序类似#xff0c;快速排序也采用了分治策略。对于一个待排序的数组A[p...r]进行快速排序#xff0c;根据分治思想#xff0c;可以分为如下三个步骤#xff1a; - 分解#xff1a;数组…快速排序 1.快速排序原理 快速排序是一种应用很广泛的排序算法与归并排序类似快速排序也采用了分治策略。对于一个待排序的数组A[p...r]进行快速排序根据分治思想可以分为如下三个步骤 - 分解数组A[p...r]被划分为两个有可能为空子数组A[p...q-1]和A[q1...r]使得A[p...q-1]中的每一个元素都小于等于A[q]而A[q]也小于等于A[q1...r]中的每一个元素。其中计算下标q也是划分过程的一部分。 -解决通过递归调用快速排序对子数组A[p...q-1]和A[q1...r]进行快速排序。 -合并注意到与归并排序不同快速排序算法中的子数组都是基于原址排序的所以不需要合并操作即数组A[p...r]已经排好了顺序。 对于快速排序来说算法的关键是找到正确的划分q该过程的伪代码如下 PARATITION(A, p, r)x A[r]i p - 1for j p to r - 1if A[j] A[r]i i 1exchange A[i] with A[j]exchange A[i 1] with A[r]return i 1 下面这张图显示了该过程。 随着算法的执行数组被划分为4个可能为空区域如下图所示 1. 若p k i则A[k] x 2. 若i1 k j-1则 A[k] x 3. 若j k r则A[k]与x的大小关系不明确 4. 若k r则A[k] r。 2.快速排序的性能 根据上面的分析快速排序的运行时间依赖于对待排序数组A[p...r]的划分是否平衡而是否划分平衡依赖于划分元素的选取如果划分是平衡的那么快速排序算法性能与归并排序一样如果划分不平衡那么快速排序的性能就接近于插入排序了注意这里是接近而不是相等 结论平均情况下快速排序的时间复杂度与最好划分情况下数量级一致均为O(nlogn)注意这里是数量级一致并不意味着时间复杂度相等 3.快速排序的随机化版本 上述的快速排序在讨论平均性能时我们假设输入数据的所有排列都是等概的。但实际情况可能并非如此有可能出现元素大小分布极不均衡的情况。可以采用一种称为随机抽样random sampling的随机化技术使主元A[r]是一个随机抽取于数组中的元素因为主元元素是随机抽取的我们期望在平均情况下对输入数组的划分是比较均衡的。采取这样的操作只需要在原来的算法上改动很小的部分即可伪代码如下 RANDOMIZED-PARTITION(A, p, r)i RANDOM(p, r)exchange A[r] with A[i]return PARATITION(A, p, r) 4.代码实现(C/C,Java,Python) 实现了快速排序最基本算法没有考虑随机化版本。 C #include stdio.h
#include stdlib.hvoid swap(int* a, int* b) {int tmp;tmp *a;*a *b;*b tmp;
}int partition(int* array, int low, int high) {int mid, index;mid low - 1;for(index low; index high; index){if(array[index] array[high]) {mid 1;swap(array[mid], array[index]);}}swap(array[mid 1], array[high]);return mid 1;
}void quicksort(int* array, int low, int high) {int mid;if(low high){mid partition(array, low, high);quicksort(array, low, mid - 1);quicksort(array, mid 1, high);}
}int main() {int *array, length, i;printf(Enter the length of array: );scanf(%d, length);array (int* )malloc(length * sizeof(int));for(i 0; i length; i)scanf(%d, array[i]);quicksort(array, 0, length - 1);for(i 0; i length; i)printf(%d , array[i]);free(array);return 0;
} C #include iostream
#include vector
using namespace std;void swap(int* a, int* b) {int tmp;tmp *a;*a *b;*b tmp;
}int partition(vectorint array, int low, int high) {int mid, index;mid low - 1;for(index low; index high; index){if(array[index] array[high]) {mid 1;swap(array[mid], array[index]);}}swap(array[mid 1], array[high]);return mid 1;
}void quicksort(vectorint array, int low, int high) {int mid;if(low high){mid partition(array, low, high);quicksort(array, low, mid - 1);quicksort(array, mid 1, high);}
}int main() {vectorint array;int length, element;cout Enter the length of array: ;cin length;cout Enter the element of array: ;for(int i 0; i length; i){cin element;array.push_back(element);}quicksort(array, 0, length - 1);for(int i 0; i length; i)cout array[i] ;return 0;
} Java import java.util.*;public class QuickSort {public static void display(IteratorInteger it) {while(it.hasNext()) {Integer element it.next();System.out.print(element );}}public static void main(String[] args) {ArrayListInteger array new ArrayListInteger();Scanner in new Scanner(System.in);System.out.print(Enter the length of array: );int length in.nextInt();System.out.print(Enter the element of array: );for(int i 0; i length; i)array.add(in.nextInt());in.close();Sort sort new Sort(array);sort.quickSort(sort.getLow(), sort.getHigh());display(array.iterator());}
}class Sort {public Sort(ArrayListInteger array) {this.array array;}public int getLow() {return 0;}public int getHigh() {return array.size() - 1;}public void quickSort(int low, int high) {int mid;if(low high) {mid partition(low, high);quickSort(low, mid - 1);quickSort(mid 1, high);}}public int partition(int low, int high) {int index low - 1;for(int i low; i high; i) {if(array.get(i) array.get(high)) {index 1;int[] list swap(array.get(index), array.get(i));array.set(index, list[0]);array.set(i, list[1]);}}int[] list swap(array.get(index 1), array.get(high));array.set(index 1, list[0]);array.set(high, list[1]);return index 1;}public int[] swap(int a, int b) {int[] list new int[2];list[0] b;list[1] a;return list;}private ArrayListInteger array;
} Python quickSort.py def swap(A, i, j):tmp A[j]A[j] A[i]A[i] tmpdef partition(A, low, high):mid low - 1for i in range(low, high):if A[i] A[high]:mid 1swap(A, mid, i)swap(A, mid 1, high)return mid 1def quickSort(A, low, high):if low high:mid partition(A, low, high)quickSort(A, low, mid - 1)quickSort(A, mid 1, high) test.py import quickSortA [8, 7, 3, 0, 5, 4, 2, 9, 6, 1, 4]
quickSort.quickSort(A, 0, len(A) - 1)
print A 转载于:https://www.cnblogs.com/zhxbao/p/quick_sort.html
