快速排序法(QuickSort)——交换类排序法(java实现)

xiaoxiao2021-02-28  71

快速排序法(Quicksort)思想与java实现

快速排序法是一种分治排序的算法,通过两个元素的交换来消除线性表中的多个逆序,将数组有计划的分为两个部分,然后再分别对两个部分进行递归进行排序。

Quicksort的基本思想如下

从线性表选取一个基准元素Key(通常选取第一个元素),在线性表两段利用指针遍历元素对key进行比较交换。从而使得key左边的元素小于等于key,key右边的元素大于Key。把key左右的元素看作两个子表,利用递归思想对子表采用上述方法进行递归,从而获得原线性表的有序列表。Quicksort的最坏时间复杂度为O(n²),最坏情况下的比较次数为n(n-1)/2。

与冒泡排序(Bubblesort)的比较

Bubblesort在扫描过程中只对相邻的两个元素进行比较,也就是说在互换两个相邻元素时只能消除一个逆序。如果通过两个非相邻元素的交换,便能够消除线性表中的多个逆序,便会大大加快排序的速度。Bubblesort的最坏时间复杂度同为O(n²),最坏情况下的比较次数为n(n-1)/2。但平均复杂度Bubblesort为O(n²),Quicksort为O(n*logn),以2为底。

快速排序法的Java实现

public class QuickSort{ public static void main(String[] args){ int arr[] = {6,5,7,2,9,10,3}; sort(arr,0,arr.length-1); pt(arr); } public static void pt(int []arr){ for(int a:arr) //遍历数组进行打印 System.out.print(a+" "); System.out.println(); } public static int quicksort(int arr[],int a,int b){ int key = arr[a]; //设置基准元素。 int p1 = a; //设置左指针 int p2 = b; //设置右指针 while(p1<p2){ while(p1<p2 && arr[p2] >= key) //从右边开始找小于key的元素,找到则停止进行交换。 p2--; arr[p1] = arr[p2]; //改变目标元素的位置。 while(p1<p2 && arr[p1] <= key) //同理,从左边开始找大于key的元素。 p1++; arr[p2] = arr[p1]; } arr[p1] = key; //完成基准元素位置的设定,此时基准元素为中位元素。 return p1; } public static void sort(int arr[],int a,int b){ //递归 if(a<b){ //限制递归次数,防止无限递归。 int mid = quicksort(arr,a,b); sort(arr,a,mid-1); sort(arr,mid+1,b); } } } //道力之限,愿力所破。

这个视频中老师对快速排序法思想的讲解还是不错的,但是代码不够简洁。

转载请注明原文地址: https://www.6miu.com/read-46365.html

最新回复(0)