wordpress7.6,深圳网站建设 乐云seo,高端网站建设公司哪家服务好,wordpress建售卖产品的网站快速排序
3 1 2 5 4 6 重复第一轮的过程#xff0c;应该得到如下序列#xff1a;
2 1 3 5 4 6 OK#xff0c;现在3已经归位。接下来需要处理3左边的序列#xff1a;
2 1 3 6 处理之后#xff0c;2已经归位#xff0c;序列“1”只有一个数#xff0c;也不需要进行任何…快速排序
3 1 2 5 4 6 重复第一轮的过程应该得到如下序列
2 1 3 5 4 6 OK现在3已经归位。接下来需要处理3左边的序列
2 1 3 6 处理之后2已经归位序列“1”只有一个数也不需要进行任何处理因此“1”也归位。
1 2 3 6 对于基数右边的序列采用和左边相同的过程最终将会得到这样的序列如下。
1 2 3 4 5 6 7 8 9 10 细心的同学可能已经发现快速排序的每一轮处理其实就是将这一轮的基准数归位直到所有的数都归位为止排序就结束了。接下来用图示的方法来展示完整的过程
快速排序之所以比较快是因为与冒泡排序相比每次的交换时跳跃式的每次排序的时候设置一个基准点将小于等于基准点的数全部放到基准点的左边将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换交换的距离就大的多了。因此总的比较和交换次数就少了速度自然就提高了。当然在最坏的情况下仍可能是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和冒泡排序是一样的都是O ( n 2 ) O(n^2)O(n 2 )它的平均时间复杂度为O ( n log 2 n ) O(n\log_2n)O(nlog 2
n)。
class QuickSort {public static void Quick_Sort(int [] x, int begin, int end){if(begin end)return;int tmp x[begin];int i begin;int j end;while(i ! j){while(x[j] tmp j i)j--;while(x[i] tmp j i)i;if(j i){int t x[i];x[i] x[j];x[j] t;}}x[begin] x[i];x[i] tmp;Quick_Sort(x, begin, i-1);Quick_Sort(x, i1, end);}
public static void main(String[] args) {
int [] arr new int[10];//定义数组Scanner sc new Scanner(System.in);for(int i0;i10;i){//赋值arr[i] sc.nextInt();}Quick_Sort(arr, 0, 9);for(int j0;j10;j){System.out.println(arr[j]);}}
}
