我要招人

去企业版

首页 > 试题广场 >

快速排序

[编程题]快速排序

热度指数：1028 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 128M，其他语言256M
算法知识视频讲解

给定一个长度为n的数组，从小到大输出每个数。

输入描述:

第一行一个整数n数组的长度。
第二行n个元素，表示数组中的数。

输出描述:

从小到大输出每个数

示例1

输入

5 
2 2 5 4 1

输出

1 2 2 4 5

算法知识视频讲解

Conan丶

func quickSort(arr []int) []int {
	return _quickSort(arr, 0, len(arr)-1)
}

func _quickSort(arr []int, left, right int) []int {
	if left < right {
		partitionIndex := partition(arr, left, right)
		_quickSort(arr, left, partitionIndex-1)
		_quickSort(arr, partitionIndex+1, right)
	}
	return arr
}

func partition(arr []int, left, right int) int {
	pivot := left
	index := pivot + 1
	for i := index; i <= right; i++ {
		if arr[pivot] > arr[i] {
			arr[i], arr[index] = arr[index], arr[i]
			index++
		}
	}
	arr[pivot], arr[index-1] = arr[index-1], arr[pivot]
	return index - 1
}

发表于 2020-08-20 11:59:56 回复(0)

C/C++

Tcyjg

#include <iostream>
using namespace std;
void quick_sort(int *a, int l, int r){
if(l >= r)return ;
int i = l - 1, j = r + 1, x = a[l + r >> 1];
while(i < j){
while(a[++i] < x);
while(a[--j] > x);
if(i < j)swap(a[i], a[j]);
}
quick_sort(a, l, j), quick_sort(a, j + 1, r);
}

int main() {
int n;
cin >> n;
int a[1000000];
for(int i = 0 ; i< n; i++)
cin >> a[i];
quick_sort(a,0,n-1);
for(int i = 0 ; i <n ; i++)
cout << a[i] << " ";
}
// 64 位输出请用 printf("%lld")

编辑于 2025-03-09 16:26:46 回复(0)

C/C++

正在卷的小辣鸡很积极

#include <iostream>
using namespace std;

int qiefen(int* a, int low, int high) {
    int mid = a[low];
    while (low < high) {
        while (low < high && a[high] >= mid) {
            high--;
        }
        a[low] = a[high];
        while (low < high && a[low] <= mid) {
            low++;
        }
        a[high] = a[low];
    }
    a[low] = mid;
    return low;
}

void kuaipai(int* a, int low, int high) {
    if (low < high) {
        int mid = qiefen(a, low, high);
        kuaipai(a, low, mid - 1);
        kuaipai(a, mid + 1, high);
    }
}

int main() {
    int n;
    cin >> n;

    int a[n];

    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    kuaipai(a, 0, n - 1);

    for (int i = 0; i < n; i++) {
        cout << a[i] << " " ;
    }
}
// 64 位输出请用 printf(\"%lld\")

发表于 2024-03-04 15:16:48 回复(0)

布朗尼尼尼

#include <bits/stdc++.h>

using namespace std;

int partition(vector<int>& nums,int left,int right)

{

if(left>=right)

{

return 0;

}

int pivot=nums[left];

int i=left;

int j=right;

while(i<j)

{

while(i<j && nums[j]>=pivot)

{

j--;

}

if(i<j) nums[i]=nums[j];

while(i<j && nums[i]<=pivot)

{

i++;

}

if(i<j) nums[j]=nums[i];

}

nums[i]=pivot;

partition(nums,left,i-1);

partition(nums,i+1,right);

}

int main()

{

int n;

cin>>n;

vector<int> nums;

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

{

int number;

cin>>number;

nums.push_back(number);

}

partition(nums,0,n-1);

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

{

if(i!=n-1)

{

cout<<nums[i]<<" ";

}

else

{

cout<<nums[i];

}

return 0;

}

发表于 2023-09-10 13:48:16 回复(0)

想上研究生

#include<iostream>

using namespace std;

const int N = 1e6 + 10;
int q[N];

void quick_sort(int q[], int l, int r){
if(l >= r){
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(){
int n;
scanf("%d", &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;

}

发表于 2023-01-17 11:06:53 回复(0)

咖啡201909101841594

#include<stdio.h>
#define MaxSize 100
void swap(int * a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
void fast_sort(int arr[],int len)
{
    int i, j;

    for (i = 0; i < len - 1; i++)
    {
        int min = i;
        for (j = i + 1; j < len; j++)//走访未排序元素
        {
            if (arr[j] < arr[min])//找到目前最小的值
                min = j;//记录最小值
        }
        swap(&arr[min], &arr[i]);//& 取地址
    }
}

int main()
{
    int i,len;
    printf("请输入数组的长度:");
    scanf("%d", &len);
    int arr[MaxSize];
    printf("请输入数组中N个元素L:");
    for (i = 0; i < len; i++)
    {
        scanf("%d",&arr[i]);
    }
    fast_sort(arr, len);

    for (int k = 0; k < len; k++)
    {
        printf("%d\n", arr[k]);
    }
}

发表于 2019-09-27 11:03:05 回复(1)

Python

林某人

n = int(input())
alist = [int(x) for x in input().split(' ')]

# 不开辟新的空间，使用双指针引用
def fast_sort(alist, first, last):
    left = first
    right = last
    # 停止标志 
    if left >= right:
        return
    mid = alist[first]
    while left < right:
        while (left < right) and (alist[right] >= mid):
            right -= 1
        alist[left]= alist[right]
        while (left < right) and (alist[left] < mid):
            left += 1
        alist[right] = alist[left]
    alist[left] = mid
    fast_sort(alist,first, left-1)
    fast_sort(alist,left+1, last)
    
fast_sort(alist,0,n-1)
c = ' '
print(c.join([str(i) for i in alist]))

发表于 2019-09-24 11:04:57 回复(0)