解题思路:
先从后面向前走,找到比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语言代码)浏览:1170 |
小九九 (C语言代码)浏览:531 |
C语言程序设计教程(第三版)课后习题7.4 (C++代码)(和输入10个数排序没有区别,直接sort即可)浏览:2098 |
【出圈】 (C语言代码)用单项循环链表浏览:773 |
C语言训练-斐波纳契数列 (C语言代码)浏览:790 |
点我有惊喜!你懂得!浏览:1395 |
C语言程序设计教程(第三版)课后习题11.12 (C语言代码)浏览:726 |
K-进制数 (C++代码)浏览:858 |
简单的a+b (C语言代码)浏览:676 |
A+B for Input-Output Practice (VI) (C++代码)浏览:418 |