输入为两行。 第一行一个整数n(1 ≤ n ≤ 100000),表示一共有n个元素 第二行为n个数,即每个元素,每个整数都在32位int范围内。以空格分隔。
输出一行,即排序之后的数组,以空格分隔,行末无空格
10 293 108 161 783 376 265 330 598 646 812
108 161 265 293 330 376 598 646 783 812
#include<bits/stdc++.h> using namespace std; int partition(vector<int> &a,int start,int end){ int small=start; for(int i=start;i<end;i++){ if(a[i]<a[end]){ swap(a[i],a[small]); small++; } } swap(a[end],a[small]); return small; } void quicksort(vector<int> &a,int start,int end){ if(start==end) return; int dex=partition(a,start,end); if(dex>start) quicksort(a,start,dex-1); if(dex<end) quicksort(a,dex+1,end); } int main(){ int n; cin>>n; vector<int> a(n); for(int i=0;i<n;i++) cin>>a[i]; quicksort(a,0,n-1); for(int i=0;i<n;i++) { if(i==0) cout<<a[i]; else cout<<' '<<a[i]; } cout<<endl; return 0; }
package com.algorithm.sort; import com.algorithm.comparator.ArrayComparator; public class QuickSort extends ArrayComparator { public static void quickSort(int[] arr,int L,int R){ //在L到R上排序 if (L<R){ int[] ints = partition(arr, L, R); quickSort(arr,L,ints[0]);//小于区继续排 quickSort(arr,ints[1],R);//大于区继续排 } } //以最后一个位置上的数做划分 //将小于最后一个数的放左边,大于最后一个数的放右边,等于的放中间 //返回排序后返回小于区最后一个数和大于区第一个数 public static int[] partition(int[] arr, int L, int R) { int less = L - 1; //小于arr[R]的最后一个索引 int more = R; //大于arr[R]的第一个索引 int curr=L; while (curr < more) { if (arr[curr] < arr[R]) { swap(arr, ++less, curr++); } else if (arr[curr] >arr[R]) { swap(arr, --more, curr); } else { curr++; } } swap(arr,R,curr); return new int[] { less + 1, more}; } public static void main(String[] args){ int[] a={4,1,2,8,6,7}; quickSort(a,0,a.length-1); for (int i = 0; i <a.length; i++) { System.out.print(a[i]+" "); } } }
#include<iostream> #include<vector> using namespace std; void quickSort(vector<int>& arr, int left, int right) { if (left >= right) return ; int p1 = left; int p2 = right; int pivot = arr[p1]; while (p1 < p2) { while (p1 < p2 && arr[p2] >= pivot) p2--; arr[p1] = arr[p2]; while (p1 < p2 && arr[p1] <= pivot) p1++; arr[p2] = arr[p1]; } arr[p1] = pivot; quickSort(arr, left, p1 - 1); quickSort(arr, p1 + 1, right); } int main() { int n; cin >> n; vector<int> arr(n, 0); for (int i=0; i<n; i++) cin >> arr[i]; quickSort(arr, 0, arr.size() - 1); for (int i=0; i<n; i++) { if (i) cout << " " << arr[i]; else cout << arr[i]; } return 0; }
#include<stdio.h> #include<string.h> #define N 100005 void QuickSort(int str[],int begin,int end){ int left = begin; int right = end; if(left>=right) return;//快排不加上终止条件就会内存过大,无限递归 int flag = str[left]; while(left<right){ while(str[right]>flag&&left<right) right--; str[left] = str[right]; while(str[left]<flag&&left<right) left++; str[right] = str[left]; } if(left == right) str[left] = flag; QuickSort(str,begin,left-1); QuickSort(str,left+1,end); } int main(){ int n,i; int a[100005]; while(scanf("%d",&n)!=EOF && n<=100000 && n>=1){ for(i=0;i<n;i++) scanf("%d",&a[i]); } QuickSort(a,0,n-1); for(i=0;i<n;i++){ if(i>0) printf(" "); printf("%d",a[i]); } }
#include<stdio.h> int a[100005],n,i; void quickSort(int,int); int main(){ for(scanf("%d",&n),i=0;i<n;i++) scanf("%d",a+i); quickSort(0,n-1); for(i=0;i<n;i++) printf("%s%d",i?" ":"",a[i]); } void quickSort(int l,int r){ if(l>=r) return; int mid=a[l],i,left=l,right=r; while(left<right){ while(left<right&&a[right]>mid) right--; a[left]=a[right]; while(left<right&&a[left]<=mid) left++; a[right]=a[left]; } a[left]=mid; quickSort(l,left-1),quickSort(left+1,r); }
#include <iostream> #include <vector> using namespace std; int Partition(vector<int> &A,int p,int r){ int x=A[r]; int i=p-1; for(int j=p;j<=r-1;++j){ if(A[j]<=x){ ++i; swap(A[i],A[j]); } } swap(A[i+1],A[r]); return i+1; } void QuickSort(vector<int> &A,int p,int r){ if(p<r){ int q=Partition(A,p,r); QuickSort(A,p,q-1); QuickSort(A,q+1,r); } } int main(){ int n; cin>>n; vector<int> A(n); for(int i=0;i<n;++i) cin>>A[i]; QuickSort(A,0,n-1); for(int i=0;i<n;++i){ cout<<A[i]; if(i!=n-1) cout<<" "; } }
def quicksort(s,left,right): l = left r = right if(left>right): return temp = int(s[left]) while(l != r): while(int(s[r])>=temp and l<r): r -= 1 while(int(s[l])<=temp and l<r): l += 1 if (l<r): t = int(s[l]) s[l] = int(s[r]) s[r] = t s[left]=int(s[l]); s[l]=temp; quicksort(s,left,l-1) quicksort(s,l+1,right) return s n = int(input()) right = n-1 s = input().split(" ") result = quicksort(s,0,right) print(" ".join(str(i) for i in result))
import java.util.Scanner; import java.util.Arrays; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int number = Integer.parseInt(in.nextLine()); String[] data = in.nextLine().split(" "); int[] a = new int[number]; for (int i = 0; i < number; i++) { a[i] = Integer.parseInt(data[i]); } quick(a, 0, a.length - 1); for (int i = 0; i < a.length; i++) { System.out.print(a[i] + " "); } } public static void quick(int a[], int l, int h) { if (l >= h) { return; } int p = sort(a, l, h); quick(a, l, p - 1); quick(a, p + 1, h); } public static int sort(int a[], int l, int h) { int t = a[h]; int i = l; for (int j = i; j < h; j++) { if (a[j] < t) { swap(a, i, j); i++; } } swap(a, i, h); return i; } public static void swap(int a[], int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; } }这个测试和提交不一样啊
#include<iostream> #include<vector> #include<algorithm> using namespace std; //单趟排序,确定key值 int PartSort(vector<int>& a,int left,int right) { //保留key值 int key=a[left]; int hole=left; while(left<right) { //找小 while(left<right&&a[right]>=key) { right--; } a[hole]=a[right]; hole=right; //找大 while(left<right&&a[left]<=key) { left++; } a[hole]=a[left]; hole=left; } a[hole]=key; return hole; } void QuickSort(vector<int>& a,int left,int right) { if(left>=right) { return; } int keyi=PartSort(a,left,right); QuickSort(a,left,keyi-1); QuickSort(a,keyi+1,right); } int main() { int n; cin>>n; vector<int> arr(n); for(int i=0;i<n;i++) { cin>>arr[i]; } QuickSort(arr,0,n-1); for(int i=0;i<n;i++) { cout<<arr[i]<<' '; } return 0; }
import java.io.*; import java.lang.Exception; import java.util.Arrays; public class Main { //标准IO public static void main(String args[]) throws Exception { BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); String str; while ((str = bf.readLine()) != null) { int len = Integer.valueOf(str); String s = bf.readLine(); String [] strs = s.split(" "); int[] arr = new int[strs.length]; for (int i = 0; i < strs.length; i++) { arr[i] = Integer.valueOf(strs[i]); } quickSort(arr, 0, arr.length-1); for (int j = 0; j < arr.length; j++) { if (j < arr.length-1) { System.out.print(arr[j]+" "); } else { System.out.println(arr[j]); } } } } public static void quickSort(int[] arr, int low, int high) { if (low >= high) { return; } int i = low; int j = high; int key = arr[low];//定义关键字 while ( i < j) {//左指针<右指针 while (arr[i] < key && i < j) { i++; } while (arr[j] > key && i < j) { j--; } int temp = arr[j]; arr[j] = arr[i]; arr[i] = temp; } arr[i] = key;//刚取出的关键字放回中间位置 quickSort(arr, low, i-1);//递归小于关键字的部分重新排序 quickSort(arr, i+1, high);//递归大于关键字的部分重新排序 } }
#include <iostream> #include <vector> using namespace std; void swap(vector<int>& a, int x, int y){ int temp = a[x]; a[x] = a[y]; a[y] = temp; } void display(vector<int> a){ for(int i = 0; i < int(a.size()); i++) cout<<a[i]<<' '; cout<<endl; } int partition1(vector<int>& a, int begin, int end){ int pivot = begin; //display(a); while(true){ while(begin < end && a[end] > a[pivot]) end--; while(begin < end && a[begin] <= a[pivot]) begin++; if(begin < end) swap(a, begin, end); else break; } swap(a, begin, pivot); pivot = begin; return pivot; } int partition2(vector<int>& a, int begin, int end){ int pivot = end; int low = begin - 1; for(int high = begin; high <= end - 1; high++){ if(a[pivot] > a[high]) swap(a, ++low, high); } swap(a, pivot, low + 1); pivot = low + 1; return pivot; } int partition3(vector<int>& a, int begin, int end){ int pivot = begin; while(begin < end){ while(begin < end && a[end] > a[pivot]) end--; swap(a, pivot, end); pivot = end; while(begin < end && a[begin] <= a[pivot]) begin++; swap(a, pivot, begin); pivot = begin; } return pivot; } void quick_sort(vector<int>& a, int begin, int end){ if(begin < end){ int pivot = partition3(a, begin, end); quick_sort(a, begin, pivot - 1); quick_sort(a, pivot + 1, end); } } int main(){ int n = 0; cin>>n; vector<int> a(n); for(int i = 0; i < n; i++) cin>>a[i]; quick_sort(a, 0, a.size() - 1); for(int i = 0; i < n; i++) cout<<a[i]<<' '; return 0; }
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner cin=new Scanner(System.in);
int number=Integer.parseInt(cin.nextLine());
String[] data=cin.nextLine().split(" ");
int[] array=new int[number];
for(int i=0;i<number;i++){
array[i]=Integer.parseInt(data[i]);
}
sort(array,0,number-1);
for(int i=0;i<number;i++){
if(i!=number-1)
System.out.print(array[i]+" ");
else System.out.print(array[i]);
}
}
public static void sort(int[] array,int lo,int hi){
if(lo>=hi)return ;
int index=partition(array,lo,hi);
sort(array,lo,index-1);
sort(array,index+1,hi);
}
public static int partition(int[] array,int lo,int hi){
int key=array[lo];
while(lo<hi){
while(array[hi]>=key&&hi>lo)hi--;
array[lo]=array[hi];
while(array[lo]<=key&&hi>lo)lo++;
array[hi]=array[lo];
}
array[hi]=key;
return hi;
}
}
#include <iostream> using namespace std; int cmp(const void *a,const void *b){ return *(int *)a - *(int *)b; } int main() { int n; cin>>n; int arr[n]; for(int i = 0;i<n;i++){ cin>>arr[i]; } qsort(arr,n,sizeof(int),cmp); for(int i = 0;i<n;i++){ cout<<arr[i]<<' '; } }
package Quick_Sort; import java.util.Arrays; import java.util.Scanner; public class Quick_Sort { public static void main(String args[]){ Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int[] arr = new int[n]; for(int i = 0 ; i < n ; i++){ arr[i] = scanner.nextInt(); } quick(arr,0,arr.length - 1); System.out.println(Arrays.toString(arr)); } public static void quick(int[] arr,int start , int end){ if(start > end){ return; } int tmp = arr[start]; int i = start; int j = end; while (i != j){ while (arr[j] >= tmp && j > i){ j--; } while (arr[i] <= tmp && i < j){ i++; } if(j > i){ int t = arr[i]; arr[i] = arr[j]; arr[j] = t; } } arr[start] = arr[i]; arr[i] = tmp; quick(arr,start,i-1); quick(arr,i+1,end); } }
#include <iostream> using namespace std; int idxnum(int* q, int l, int r) { int idx = q[l]; while (l < r) { while (l < r && q[r] >= idx) { --r; } q[l] = q[r]; while (l < r && q[l] <= idx) { ++l; } q[r] = q[l]; } q[l] = idx; return l; } void quick_sort(int* q, int l, int r) { if (l >= r)return ; int idx = idxnum(q, l, r); quick_sort(q, l, idx - 1); quick_sort(q, idx + 1, r); } int main() { int n = 0; scanf("%d", &n); int q[n]; for (int i = 0; i < n; i++) { scanf("%d", &q[i]); } int l = 0, r = n - 1; quick_sort(q, l, r); for (int i = 0; i < n; i++) { printf("%d ", q[i]); } printf("\n"); }
import java.util.Scanner; import java.io.*; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) throws Exception{ BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); String str = null; while ((str = bf.readLine()) != null) { int len = str.length(); String[] strs = str.split(" "); int[] arr = new int[strs.length]; for (int i=0; i < strs.length; i++) { arr[i] = Integer.valueOf(strs[i]); } quickSort(arr, 0, arr.length-1); for (int j=0; j < arr.length; j++) { if (j <= arr.length-1) { System.out.printf("%d ", arr[j]); } else { System.out.println(arr[j]); } } } } private static void quickSort(int[] arr, int start, int end) { int i = start; int j = end; int baseNumber = arr[start]; while (i < j) { while (i < j && arr[i] < baseNumber) { i++; } while (i baseNumber) { j--; } if (i < j && arr[i] == arr[j]) { i++; } else { int tempNumber = arr[i]; arr[i] = arr[j]; arr[j] = tempNumber; } } if (i - 1 > start) quickSort(arr, start, i - 1); if (j + 1 < end) quickSort(arr, j + 1, end); } }