写在前面:
思维导图: 1,快速排序概念通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。主要采用 2,算法思路我们先搞清楚这个堆排序思想,先把逻辑搞清楚,不着急写代码。 我们首先有一个无序数组,比方说 int[] arr={4,2,8,0,5,7,1,3,9}; 2.1,第一步,取基准数基准数(枢轴),取数组的第一个元素,此时基准数:arr[0]=4 并定义两个变量i和j分别指向无序数组的第一个元素start和最后一个元素end。 //起始 int i=start; int j=end; //获取基准数 int temp=arr[start]; 2.2,第二步,分区过程分区过程,将比基准数大的数全放到它的右边,比基准数小的或者相等的数全放到它的左边。 我们首先把第一个元素arr[0]=4定义为基准元素,此时数组第一个位置就是坑,那么我们要从数组的右边向左开始查找小于基准数的元素,并与坑互换位置。 while(i<j){ //从右向左去找比基准数小的 while(i<j&&arr[j]>=temp){ j--; } //判断相等,填坑 if(i<j){ arr[i]=arr[j]; i++; } } 换好位置之后,现在转换,从数组的左边向右边查找比基准数大的元素: while(i<j){ //从右向左去找比基准数小的 while(i<j&&arr[j]>=temp){ j--; } //判断相等,填坑 if(i<j){ arr[i]=arr[j]; i++; } //从左向右去找比基准数大的 while(i<j&&arr[i]<temp){ i++; } //判断相等,填坑 if(i<j){ arr[j]=arr[i]; j--; } } 换好位置之后,现在又重新开始从数组右边向左边开始查找,比基准数小的元素: 不断重复此类操作,直到分成左右两个分区,再把基准数填入坑中,这样第一趟排序完成。如下: //把基准数放到i=j的位置 arr[i]=temp; 2.3,第三步,对两个区间重复进行分区操作这里,我们对分好的两个区间重复进行上述分区操作,直到每个区间只有一个元素为止。 重复进行以上操作,直到左右两边分区都是有序排列,整个排序过程也就完成了: //对左半边部分进行快排 QuickSort(arr,start,i-1); //对右半边部分进行快排 QuickSort(arr,i+1,end); 3,完整代码import java.util.Arrays; public class Quick_Sort { public static void main(String[] args) { int[] arr=new int[]{4,2,8,0,5,7,1,3,9}; System.out.println(Arrays.toString(QuickSort(arr,0,arr.length-1))); } public static int[] QuickSort(int[] arr,int start,int end){ //起始 int i=start; int j=end; //获取基准数 int temp=arr[start]; //i<j为循环条件 if(i<j){ while(i<j){ //从右向左去找比基准数小的 while(i<j&&arr[j]>=temp){ j--; } //判断相等,填坑 if(i<j){ arr[i]=arr[j]; i++; } //从左向右去找比基准数大的 while(i<j&&arr[i]<temp){ i++; } //判断相等,填坑 if(i<j){ arr[j]=arr[i]; j--; } } //把基准数放到i=j的位置 arr[i]=temp; //对左半边部分进行快排 QuickSort(arr,start,i-1); //对右半边部分进行快排 QuickSort(arr,i+1,end); } return arr; } } 4,算法分析4.1,时间复杂度快速排序最坏时间复杂度是 4.2,空间复杂度空间复杂度是 4.3,算法稳定性快速排序是不稳定的排序算法。因为我们无法保证相等的数据按顺序被扫描到和按顺序存放。 最坏时间复杂度是 4.2,空间复杂度空间复杂度是 4.3,算法稳定性快速排序是不稳定的排序算法。因为我们无法保证相等的数据按顺序被扫描到和按顺序存放。 |
|
来自: 昵称45893186 > 《待分类》