首页 > 试题广场 >

排序

[编程题]排序
  • 热度指数:42539 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
    对输入的n个数进行排序并输出。

输入描述:
    输入的第一行包括一个整数n(1<=n<=100)。
    接下来的一行包括n个整数。


输出描述:
    可能有多组测试数据,对于每组数据,将排序后的n个整数输出,每个数后面都有一个空格。
    每组测试数据的结果占一行。
示例1

输入

4
1 4 3 2

输出

1 2 3 4 

Go 语言 - 归并排序

package main

import "fmt"

// 归并排序
func mergeSort(nums []int) []int {
    numsLen := len(nums)
    if numsLen < 2 {
        return nums
    }
    
    middleIndex := numsLen / 2
    left := nums[: middleIndex]
    right := nums[middleIndex:]
    return merge(mergeSort(left), mergeSort(right))
}

func merge(left, right []int) []int {
    var result []int
    for len(left) != 0 && len(right) != 0 {
        if left[0] <= right[0] {
            result = append(result, left[0])
            left = left[1: ]
        } else {
            result = append(result, right[0])
            right = right[1: ]
        }
    }
    
    if len(left) != 0 {
        result = append(result, left...)
    }
    
    if len(right) != 0 {
        result = append(result, right...)
    }
    return result
}

func main(){
    var n int
    fmt.Scan(&n)
    
    nums := make([]int, n)
    for i := 0; i < n; i++ {
        var tmp int
        fmt.Scan(&tmp)
        nums[i] = tmp
    }
    
    res := mergeSort(nums)
    for _, num := range res {
        fmt.Print(num, " ")
    }
}

Go 语言 - 快速排序

package main

import "fmt"

// 快速排序
func quickSort(nums []int)[]int{
	return _quickSort(nums, 0, len(nums) - 1)
}

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

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

func main(){
	var n int
	fmt.Scan(&n)

	nums := make([]int, n)
	for i := 0; i < n; i++ {
		var tmp int
		fmt.Scan(&tmp)
		nums[i] = tmp
	}

	res := quickSort(nums)
	for _, num := range res {
		fmt.Print(num, " ")
	}
}



发表于 2020-08-29 16:33:28 回复(0)
#include<stdio.h>
int main()
{
    int n,a[100],i,j,t;
    scanf("%d",&n);
    for(i=0;i<n;i++) scanf("%d",&a[i]);
    for(i=0;i<n-1;i++)//冒泡的趟数
        for(j=0;j<n-1-i;j++)//比较的次数
            if(a[j]>a[j+1])
            {//交换
                t=a[j];a[j]=a[j+1];a[j+1]=t;
            }
    for(i=0;i<n;i++) printf("%d ",a[i]);
}

发表于 2020-03-29 14:46:40 回复(1)
Java ,使用JavaAPI,冒泡排序,选择排序,插入排序,堆排序,归并排序,快速排序 七种解法
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
    static int[] array;
    static int n;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        array = new int[n];
        for (int i = 0; i < n; i++) array[i] = scanner.nextInt();
//        apiSort();
//        bubbleSort();
//        selectSort();
//        insertSort();
//        heapSort();
//        mergeSort(0, n - 1);
        quickSort(0, n - 1);
        for (int i : array) System.out.print(i + " ");
    }

    // 使用Java APi
    static void apiSort() {
        Arrays.sort(array);
    }

    // 交换两个数
    static void swap(int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    // 冒泡排序
    static void bubbleSort() {
        // 每趟往前归位一个最小值
        for (int i = 1; i < n; i++)
            for (int j = n - 1; j >= i; j--)
                if (array[j] < array[j - 1]) swap(j, j - 1);
    }

    // 选择排序
    static void selectSort() {
        for (int i = 0; i < n - 1; i++) {
            int k = i;
            for (int j = i; j <= n - 1; j++)
                if (array[j] < array[k]) k = j;
            swap(k, i);
        }
    }

    // 插入排序
    static void insertSort() {
        for (int i = 1; i < n; i++) {
            for (int j = i; j > 0; j--) {
                if (array[j] < array[j - 1]) swap(j, j - 1);
                else break;
            }
        }
    }

    // 堆排序
    static void heapSort() {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int i : array) minHeap.add(i);
        for (int i = 0; i < n; i++) array[i] = minHeap.poll();
    }

    // 归并排序
    static void mergeSort(int i, int j) {
        if (i >= j) return;
        int mid = (i + j) >> 1;
        mergeSort(i, mid);
        mergeSort(mid + 1, j);
        merge(i, mid, j);
    }

    static void merge(int i, int mid, int j) {
        int[] temp = new int[n];
        int l = i;
        int r = mid + 1;
        int t = i;
        while (l <= mid && r <= j) temp[t++] = array[l] <= array[r] ? array[l++] : array[r++];
        while (l <= mid) temp[t++] = array[l++];
        while (r <= j) temp[t++] = array[r++];
        System.arraycopy(temp, i, array, i, j - i + 1);
    }

    // 快速排序
    static void quickSort(int i, int j) {
        if (i >= j) return;
        int pivot = partition(i, j);
        quickSort(i, pivot - 1);
        quickSort(pivot + 1, j);
    }

    static int partition(int i, int j) {
        int v = array[i];
        int l = i + 1;
        int r = j;
        while (true) {
            while (l <= j && array[l] <= v) l++;
            while (r >= i + 1 && array[r] >= v) r--;
            if (l > r) break;
            swap(l++, r--);
        }
        swap(i, r);
        return r;
    }
}


发表于 2020-03-17 20:51:44 回复(0)
# include<stdio.h>
# include<algorithm>
using namespace std;
int main()
{
    int n;
    int buf[10000];
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=0;i<n;i++)
        {
            scanf("%d",&buf[i]);
        }
        sort(buf,buf+n);
        for(int i=0;i<n;i++)
        {
            printf("%d ",buf[i]);
        }
        printf("\n");
    }
    return 0;
}
// 如果遇到N比较大的情况下,可以用sort函数
发表于 2018-02-15 12:31:02 回复(0)
注意一下每个数字后面都有空格(包括一行末尾的数字后面也有空格)即可
#include <stdio.h>
#include <algorithm>
using namespace std;
int main() {
    int n, a[101];
    while(scanf("%d", &n)!=EOF) {
        for(int i=0; i<n; i++) scanf("%d", &a[i]);
        sort(a, a+n);
        for(int i=0; i<n; i++) printf("%d ", a[i]);
        printf("\n");
    }
    return 0;
}

编辑于 2018-02-06 20:26:45 回复(0)
#include <stdio.h>
#include <algorithm>
using namespace std;

int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        int buf[100];
        for (int i=0; i<n; i++)
            scanf("%d", &buf[i]);
        sort(buf, buf+n);
        for (int i=0; i<n; i++)
            printf("%d ",buf[i]);
        printf("\n");
    }
    return 0;
}
发表于 2018-02-02 12:35:50 回复(0)
int main(){
    int buf[100],n,i,j;
    while(scanf("%d",&n)!=EOF){
        for(i=0;i<n;i++)
            scanf("%d",&buf[i]);
        sort(buf,buf+n);
        for(j=0;j<n;j++)
            printf("%d ",buf[j]);
        printf("\n");
    }
    return 0;
}

1.使用c++库algorithm实现排序
2.while控制一轮输入   ,int n 和n 个数是一个整体  因此while 循环的花括号需要将控制一轮循环的代码括起来 输入n为EOF时whlie条件失效return 0;结束整个程序进程
发表于 2018-01-15 11:21:44 回复(0)
#include<stdio.h>
int main()
{
    int a[100],n,i,j,t;
    while(scanf("%d",&n)!=EOF)
    {
        for(i=0;i<n;i++)
        scanf("%d",&a[i]);
        for(i=0;i<n;i++)
        for(j=0;j<n-i-1;j++)
            if(a[j]>a[j+1])
        {
            t=a[j];
            a[j]=a[j+1];
            a[j+1]=t;
        }
        for(i=0;i<n;i++)
            printf("%d ",a[i]);
        printf("\n");
    }
    return 0;
}
发表于 2017-12-30 21:16:29 回复(0)
import java.util.*;
 
public class Main{
     
    public static void quickSort(int[] arr, int first, int last){
        if(first >= last) return;
        int pivot = arr[first], l = first, h = last;
        while(l < h){
            while(l < h && pivot <= arr[h]) h--;
            arr[l] = arr[h];
            while(l < h && pivot >= arr[l]) l++;
            arr[h] = arr[l];
        }
        arr[l] = pivot;
        quickSort(arr, first, l - 1);
        quickSort(arr, l + 1, last);
    }
     
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int[] arr = new int[101];
        while(in.hasNext()){
            int n = in.nextInt();
            for(int i = 0; i < n; i++){
                arr[i] = in.nextInt();
            }
            quickSort(arr, 0, n-1);
            for(int i = 0; i < n; i++){
                System.out.print(arr[i] + " ");
            }
            System.out.println();
        }
    }
}

编辑于 2017-05-20 16:58:29 回复(0)



我就不明白了。同样的程序,为什么输出结果就是不一样o(╯□╰)o
发表于 2017-03-23 21:52:38 回复(7)
#include <stdio.h>
#include <stdlib.h>   //包含qsort的头文件

//比较函数
int Cmp(const void *pa, const void *pb)
{
return *(int*)pa > *(int*)pb;
}

int main(){

    int n; 
    int arr[10000];

        //输入数据
    while (scanf("%d", &n) != EOF){
        for (int i = 0; i < n; i++)    {            
            scanf("%d", &arr[i]);
        }

    //使用qsort排序算法
    qsort(arr, n, sizeof(int), Cmp);

    //输出数据
    for (i=0; i<n; i++){
        printf("%d ", arr[i]);
    }
    printf("\n");
    }
    return 0;
}
发表于 2018-02-08 16:27:05 回复(0)
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

const int maxn = 102;

int num[maxn] = {0};

int main()
{
    int n;
    while(cin >> n)
    {
        for(int i = 0; i < n; ++i)
        {
            cin >> num[i];
        }
        sort(num, num+n);
        for(int i = 0; i < n; ++i)
        {
            cout << num[i] << " ";
        }
        cout << endl;
    }

    return 0;
}


发表于 2016-08-07 10:18:09 回复(0)

无论用哪个语言,使用快排算法的时候遇到了一个小坑,这次的测试数据也充分告诉我这个小坑的重要性。。。 大部分的快排写法中都有一个while(l<r && data[r]>= base)r--;类似这样的过程,请注意这个while循环中一定要使用>=或<=,如果你去掉了=号,你可以试试看是什么结果。。 超时! 这个=号在细节上是非常重要的。

编辑于 2017-03-23 16:14:46 回复(5)

python两行解法,注意后面还要加个空格 。

while True:
    try:
        a,b=input(),map(int,input().split())
        print(" ".join(map(str,sorted(b)))+" ")
    except:
        break
发表于 2017-10-01 16:36:19 回复(3)
#include <stdio.h>
#include <algorithm>
using namespace std;
void bubblesort(int buf [],int n){
int tmp;
        for(int i=0;i<n;++i)
        {
            for(int j=0;j<n-i-1;++j)
            {
                if(buf[j]>buf[j+1])
                {
                    tmp=buf[j+1];
                    buf[j+1]=buf[j];
                    buf[j]=tmp;
                }
            }   
        }
        return;
}
void selectsort(int buf [],int n){
int m=0,t;
        for(int i=0;i<n;++i)
        {
            m=n-i-1;
            for(int j=0;j<n-i;++j)
            {
                if(buf[j]>buf[m])
                {
                    m=j;
                }
            }   
            t=buf[n-1-i];
            buf[n-1-i]=buf[m];
            buf[m]=t;
        }
        return;
}
void qsort(int a[],int low,int high)
{
    if(low>=high)return;
    int pivot=a[low],l=low,h=high;
    while(l<h)
    {
        while(l<h&&pivot<=a[h])
            --h;
        a[l]=a[h];
        while(l<h&&pivot>=a[l])
            ++l;
        a[h]=a[l];
    }
    a[l]=pivot;
    qsort(a,low,l-1);
    qsort(a,l+1,high);
}
int main()
    {
        int n;
        int buf[100];
        while(scanf("%d",&n)!=EOF)
        {
            for(int i=0;i<n;++i)
            {
                scanf("%d",&buf[i]);
            }
        //sort(buf,buf+n);内置快排函数
        //bubblesort(buf,n);冒泡排序
        //selectsort(buf,n);选择排序
        qsort(buf,0,n-1);手动快排函数
        for(int i=0;i<n;++i)
            printf("%d ",buf[i]);
        printf("\n");
        }
            return 0;
    }
效率:
冒泡 3ms 384k ...
选择 3ms 372k ...
手动快排 2ms 376k;3ms 384k;...
自动快排 3ms 364k;3ms 384k;...
测试用例不同 效率会有些许变化




发表于 2018-01-06 17:00:18 回复(1)
学到四种排序,开心
1.冒泡排序
#include<bits/stdc++.h> //万能头
using namespace std;
int main() {
	int n;
	int m[100];
	while (cin >> n) {
		for (int i = 0; i < n; i++) {
			cin >> m[i];
		}
		for (int i = 0; i < n - 1; i++) {
			for (int j = 0; j < n - i - 1; j++) {
				if (m[j] > m[j + 1]) {
					int temp = m[j];
					m[j] = m[j + 1];
					m[j + 1] = temp;
				}
			}
		}
		for (int i = 0; i < n; i++) {
			cout << m[i] << " ";
		}
	}
	return 0;
}
2.选择排序
#include<bits/stdc++.h>
using namespace std;
int main() {
	int n;
	int m[100];
	while (cin >> n) {
		for (int i = 0; i < n; i++) {
			cin >> m[i];
		}
		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				if (m[i] > m[j]) {
					int temp = m[i];
					m[i] = m[j];
					m[j] = temp;
				}
			}
		}
		for (int i = 0; i < n; i++) {
			cout << m[i] << " ";
		}
	}
	return 0;
}
3.内置sort函数
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    int m[100];
    while(cin>>n){
        for(int i=0;i<n;i++){
            cin>>m[i];
        }
        sort(m,m+n); //需要调用#include<algorithm>
        for(int i=0;i<n;i++){
            cout<<m[i]<<" ";
        }
    }
    return 0;
}
4.手动快速排序qsort函数
#include<bits/stdc++.h>
using namespace std;
int cmp(const void*a,const void*b) {
	return *(int*)a - *(int*)b;//升序
	//return *(int*)a - *(int*)b;//降序
}
int main() {
	int n;
	int m[100];
	while (cin >> n) {
		for (int i = 0; i<n; i++) {
			cin >> m[i];
		}
		qsort(m, n,sizeof (m[0]),cmp);//需要调用#include<algorithm>
		for (int i = 0; i<n; i++) {
			cout << m[i] << " ";
		}
	}
	return 0;
}

发表于 2020-02-17 17:17:37 回复(1)
//选择排序+冒泡排序
#include <iostream>
using namespace std;
int main(){
    int n;
    while(cin>>n){
        int i,j,a[100];
        for(i=0;i<n;i++)
            cin>>a[i];
        //选择排序
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                if(a[i]>a[j]){
                    int temp=a[j];
                    a[j]=a[i];
                    a[i]=temp;
                }
            }
        }
        //冒泡排序
        for(int i=0;i<n-1;i++){
            for(int j=0;j<n-1-i;j++){
                if(a[j]>a[j+1]){
                    int temp=a[j];
                    a[j]=a[j+1];
                    a[j+1]=temp;
                }
            }
        }
        for(i=0;i<n;i++){
            cout<<a[i]<<" ";            
        }
        cout<<endl;           
    }
    return 0;
}    
//或者用C++自带的排序函数
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
    int n;
    while(cin>>n){
        int i,j,a[100];
        for(i=0;i<n;i++)
            cin>>a[i];
        sort(a,a+n);
        for(i=0;i<n;i++){
            cout<<a[i]<<" ";            
        }
        cout<<endl;           
    }
    return 0;
}

编辑于 2017-12-04 10:57:52 回复(0)
写了好几种排序,练一练
#include <iostream>
#include <vector>

using namespace std;
//int* simple_swap_sort(int *a,int n);           //简单的交换排序
//int* bubble_sort(int* a,int n);                  //冒泡排序
//int* simple_select_sort(int *a,int n);           //简单的选择排序
//int* simple_insert_sort(int *a,int n);           //简单的插入排序
//int* shell_sort(int *a,int n);                  //希尔排序
//int* merge_sort(int *a,int n);                  //归并排序配合合并函数使用  ps:这递归写的好烂
//int* merge(int *a,int *b,int a_n,int b_n);
int* quick_sort(int *a,int n);                  //快速排序


void Print(int a[],int n);         //输出函数

int main(){
    int n,value;
    cin>>n;
    int *arr=new int[n];
    for(int i=0;i<n;i++){
        cin>>value;
        arr[i]=value;
    }
    Print(quick_sort(arr,n),n);
//    Print(merge_sort(arr,n),n);
//    Print(shell_sort(arr,n),n);
//    Print(simple_insert_sort(arr,n),n);
//    Print(simple_swap_sort(arr,n),n);
//    Print(simple_select_sort(arr,n),n);
//    Print(bubble_sort(arr,n),n);
    delete []arr;
    return 0;
}

int* quick_sort(int *a,int n){
    if(n<1)
        return a;
    int i=0,j=n-1;
    int temp=*a,change;
    while(i<j){
        while(*(a+j)>=temp&&i<j){
            --j;
        }
        while(*(a+i)<=temp&&i<j){
            ++i;
        }
        if(i<j){
            change=*(a+i);
            *(a+i)=*(a+j);
            *(a+j)=change;
        }
    }
    *a=*(a+i);
    *(a+i)=temp;
    quick_sort(a,i);
    quick_sort(a+i+1,n-i-1);
    return a;
}

//int* merge(int *a,int *b,int a_n,int b_n){
//    int i=0,j=0,n=0,len=a_n+b_n;
//    int* result=new int[len];
//    while(i<a_n&&j<b_n){
//        if(a[i]<b[j]){
//            result[n]=a[i];
//            ++i;
//            ++n;
//        }else{
//            result[n]=b[j];
//            ++j;
//            ++n;
//        }
//    }
//    while(i<a_n){
//        result[n]=a[i];
//        ++i;
//        ++n;
//    }
//    while(j<b_n){
//        result[n]=b[j];
//        ++j;
//        ++n;
//    }
//    for(int i=0;i<len;++i){
//        *(a+i)=result[i];
//    }
//    delete[] result;
//    return a;
//}


//int* merge_sort(int *a,int n){
//    if(n<2){
//        return a;
//    }
//    int *right=a;
//    int *left=a+n/2;
//    merge_sort(right,n/2);
//    merge_sort(left,n-n/2);
//    merge(right,left,n/2,n-n/2);
//    return a;
//}


//int* shell_sort(int *a,int n){
//    int k,temp;
//    for(int gap=n/2;gap>0;gap/=2){
//        for(int i=0;i<gap;++i){
//            for(int j=i;j<n;j+=gap){                            //内层是插入排序
//                temp=*(a+j);
//                for(k=j;(k>i)&&(*(a+k-gap)>temp);k-=gap){
//                    *(a+k)=*(a+k-gap);
//                }
//                *(a+k)=temp;
//            }
//        }
//    }
//    return a;
//}


//int* simple_insert_sort(int *a,int n){
//    int temp,k;
//    for(int i=1;i<n;++i){
//        temp=*(a+i);
//        for(k=i;(*(a+k-1)>temp)&&(k>0);--k){
//            *(a+k)=*(a+k-1);
//        }
//        *(a+k)=temp;
//    }
//    return a;
//}


//int* simple_select_sort(int *a,int n){
//    int temp,min;
//    for(int i=0;i<n;++i){
//        min=i;
//        for(int j=i;j<n;++j){
//            if(*(a+min)>*(a+j)){
//                min=j;
//            }
//        }
//        temp=*(a+i);
//        *(a+i)=*(a+min);
//        *(a+min)=temp;
//    }
//    return a;
//}


//int* bubble_sort(int* a,int n){
//    int temp;
//    for(int i=0;i<n;++i){
//        int flag=0;
//        for(int j=0;j<n-i-1;++j){
//            if(*(a+j)>*(a+j+1)){
//                temp=*(a+j);
//                *(a+j)=*(a+j+1);
//                *(a+j+1)=temp;
//                ++flag;
//            }
//        }
//        if(!flag)
//            break;
//    }
//    return a;
//}


//int* simple_swap_sort(int *a,int n){
//    int temp;
//    for(int i=0;i<n;++i){
//        for(int j=i;j<n;++j){
//            if(*(a+i)>*(a+j)){
//                temp=*(a+j);
//                *(a+j)=*(a+i);
//                *(a+i)=temp;
//            }
//        }
//    }
//    return a;
//}


void Print(int a[],int n){
    for(int i=0;i<n;++i){
        cout<<a[i]<<' ';
    }
    cout<<endl;
}


编辑于 2020-03-09 12:41:30 回复(0)

/**  * 快速排序  * 第一记录为枢轴  * @param a 需要排序的数组  * @param low 数组的起始下标  * @param high 数组的末尾下标  */
public static void QSort(int a[], int low, int high) { if(low >= high) return; int pivot = a[low], l = low, h = high; for(; l < h; ) { for(; l < h && a[h] >= pivot; h--); a[l] = a[h]; for(; l < h && a[l] <= pivot; l++); a[h] = a[l]; } a[l] = pivot; QSort(a, low, l - 1); QSort(a, l + 1, high); }

编辑于 2016-06-27 22:13:12 回复(2)
//冒泡排序
#include<stdio.h>
int main(){
    int n;
    scanf("%d",&n);
    int arr[10000]={};
    for(int i=0;i<n;i++){
        scanf("%d",&arr[i]);
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n-1-i;j++){
            if(arr[j+1]<arr[j]){
                int temp;
                temp=arr[j+1];
                arr[j+1]=arr[j];
                arr[j]=temp;}
        }}
    for(int i=0;i<n;i++){
        printf("%d ",arr[i]);}
    return 0;}
//选择排序
#include<stdio.h>
int main(){
    int n;
    scanf("%d",&n);
    int arr[10000]={};
    for(int i=0;i<n;i++){
        scanf("%d",&arr[i]);
    }int k;
    for(int i=0;i<n;i++){
    k=i;
        for(int j=i+1;j<n;j++){
            if(arr[k]>arr[j])k=j;
            
        }
        if(k!=i){
            int temp;
            temp=arr[i];
            arr[i]=arr[k];
            arr[k]=temp;
    }
    }
    
    for(int i=0;i<n;i++){
        printf("%d ",arr[i]);}
    return 0;}


编辑于 2022-11-12 22:12:02 回复(0)