快速排序_欢聚集团笔试题

迪拜塔下≒仰望你的笑容.

#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;
}

编辑于 2018-04-03 12:12:17 回复(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]+" ");
        }
    }
}

发表于 2019-12-13 00:26:27 回复(2)

Spectre_

#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;
}

发表于 2019-10-09 10:23:19 回复(0)

C/C++

Smoothing

#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]);
    }
}

编辑于 2018-03-26 15:53:25 回复(0)

元气の悟空

#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);
}

编辑于 2017-11-01 09:45:59 回复(0)

♀琪寶、

#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<<" ";
	}
}

发表于 2017-09-03 19:36:48 回复(0)

lalalaaaxxx

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))

发表于 2017-09-03 10:02:08 回复(1)

牛客39792925号

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;
    }
}

这个测试和提交不一样啊

发表于 2023-09-03 03:27:23 回复(0)

souLinya

#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;
}

发表于 2023-02-22 16:56:52 回复(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);//递归大于关键字的部分重新排序
    }
}

发表于 2020-06-30 20:19:20 回复(0)

牛客144501780号

#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;
}

发表于 2020-06-08 10:47:57 回复(1)

趁现在赶快回家

这道题出错了，有道题显示970个输入，只给了683个输入

发表于 2018-03-23 15:06:40 回复(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;
    }
}

发表于 2017-09-04 01:14:51 回复(0)

Java

牛客932816400号

import java.util.*;

public class Main{

public static void quickSort(int[] arr,int left,int right){

if(left > right){

return ;

}

int l = left;

int r = right;

int pivot = arr[(left + right) / 2];

while(l < r){

while(arr[l] < pivot){

l++;

}

while(arr[r] > pivot){

r--;

}

if(l == r){

break;

}

int temp = arr[l];

arr[l] =arr[r];

arr[r] = temp;

if(arr[l] == pivot){

r--;

}

if(arr[r] == pivot){

l++;

}

if(l == r){

l++;

r--;

}

quickSort(arr,left,r);

quickSort(arr,l,right);

}

public static void main(String[] args){

Scanner sc = new Scanner(System.in);

int n = sc.nextInt();

int[] arr = new int[n];

for(int i = 0;i < arr.length;i++){

arr[i] = sc.nextInt();

}

quickSort(arr,0,arr.length-1);

for(int i = 0;i < arr.length-1;i++){

System.out.print(arr[i]+" ");

}

System.out.print(arr[arr.length-1]);

}

编辑于 2024-02-05 19:39:22 回复(0)

苏多莉亚

#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]<<' ';
    }
}

发表于 2023-12-05 10:43:40 回复(0)

牛客546663752号

#include <iostream>

using namespace std;

const int N=1e6+10;

int n;

int q[N];

void quick_sort(int q[],int l,int r)

{

if(r<=l) return ;

int x=q[l],i=l-1,j=r+1;

while(i<j)

{

do ++i;while(q[i]<x);

do --j;while(q[j]>x);

if(i<j)

swap(q[i],q[j]);

}

quick_sort(q,l,j);

quick_sort(q,j+1,r);

}

int main() {

scanf("%d/n",&n);

for(int i=0;i<n;i++)

{

scanf("%d ",&q[i]);

}

quick_sort(q,0,n-1);

for(int i=0;i<n;i++)

{

printf("%d ",q[i]);

}

return 0;

}

// 64 位输出请用 printf("%lld")

发表于 2023-09-11 19:00:48 回复(0)

thanks__start

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);  }
}

发表于 2023-07-09 10:23:52 回复(0)

lushij

#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");
}

发表于 2023-04-14 09:53:16 回复(0)

犯大吴疆土

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);
    }
}

发表于 2023-04-05 17:39:08 回复(0)

翛201808011926204

#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;

}

int partition(vector<int>& a, int begin, int end)

{

int x = a[end], i = begin - 1;

for (int j = begin; j < end; ++j) {

if (a[j] <= x) {

swap(a[++i], a[j]);

}

swap(a[i + 1], a[end]);

return i+1;

}

void quick_sort(vector<int>& a, int begin, int end){

if(begin < end){

int key = partition(a, begin, end);

quick_sort(a, begin, key - 1);

quick_sort(a, key + 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;

}

发表于 2023-04-02 21:46:33 回复(0)

快速排序

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题