解题思路:
先从后面向前走,找到比5小的放前面,再从前面向后走,找到比5大的放后面,直到L=R;
输入数字 | 5 | 2 | 3 | 7 | 9 | 1 | 6 | 4 | 8 |
L | R | ||||||||
步骤1: | 4 用4取代 | 2 | 3 | 7 | 9 | 1 | 6 | 发现4<5,R走到这里,这里已经留空 | 8 |
步骤2: | 4 | 2 | 3 | 发现7>5,R走一步,现在是L走到这里 | 9 | 1 | 6 | 7 7填空 | 8 |
步骤3: | 4 | 2 | 3 | 1 1填空 | 9 | 发现1<5,L走完,现在R走到这里 | 6 | 7 | 8 |
步骤4: | 4 | 2 | 3 | 1 | 发现9>5,R走完,现在是L走到这里 | 9 9填空 | 6 | 7 | 8 |
步骤5: | 4 | 2 | 3 | 1 | 5 把5放这里 | 9 | 6 | 7 | 8 |
得到:4 2 3 1 5 9 6 7 8 再这样下去
注意事项:看不懂去B站 https://www.bilibili.com/video/BV1nr4y1P7d6?share_source=copy_web
参考代码:
#include<bits/stdc++.h> using namespace std; int get_mid(int arr[],int left,int right) { int pivot=arr[left]; while(left<right) { while(arr[right]>pivot&&left<right) right--; arr[left]=arr[right]; while(arr[left]<=pivot&&left<right) left++; arr[right]=arr[left]; } arr[left]=pivot; return left; } void quick_sort(int arr[],int left,int right) { if(left<right) { int mid=get_mid(arr,left,right); quick_sort(arr,left,mid-1); quick_sort(arr,mid+1,right); } } int main() { int n,i,a[100000]; scanf("%d",&n); for(i=0;i<n;i++) { scanf("%d",&a[i]); } quick_sort(a,0,n-1); for(i=0;i<n;i++) { printf("%d ",a[i]); } return 0; }
0.0分
2 人评分
C二级辅导-公约公倍 (C语言代码)浏览:1508 |
C语言训练-计算t=1+1/2+1/3+...+1/n (C语言代码)浏览:904 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:632 |
循环入门练习5 (C语言代码)浏览:829 |
简单的a+b (C语言代码)浏览:572 |
C二级辅导-同因查找 (C语言代码)浏览:563 |
剔除相关数 (C语言代码)浏览:1084 |
发工资咯 (C语言代码)浏览:792 |
ACM俱乐部密码浏览:935 |
老王赛马 (C语言代码)浏览:1559 |