首页 > 试题广场 >

选择排序

[编程题]选择排序

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

排序是处理很多问题的预处理部分。
之前的题目中，数值范围比较小，通过记录每个数值出现的次数，再按照数值从小到大，该数值出现多少次，就输出多少个。
这种方法，不适用于数值范围很大的情况，因为数组无法开。不能开出A[100000000]这样1亿大小的数组，数组的总大小要控制在3千万以内。
除了计数排序，还有很多种排序方法。下面来介绍一种简单的排序算法，选择排序。
选择排序的思想是：从前往后依次得到每个位置上的数。对于第i个位置，在[i+1,n]这些位置中，找到一个最小值，记录它的位置k。把A[i]和A[k]的值进行交换。

for(i=1;i<=n;i++){//依次得到每个位置上的数

k=i;//先设这个位置上的数不动，就是最小的那个

for(j=i+1;j<=n;j++)//在[i+1,n]这个区间找最小值的位置

if(A[j]<a[k])k=j;

if(k!=i){//交换A[i]和A[k]

t=A[i];

a[i]=A[k];

a[k]=t;

}

}

输入描述:

第一行一个整数n，表示要排序的数个数。
第二行n个元素，表示待排序的元素。

输出描述:

输出n个数字，表示排序后的数字。

示例1

输入

5
-1 2 1 4 3

输出

-1 1 2 3 4

备注:

数据范围：，序列中的元素范围在之间。

算法知识视频讲解

thanks__start

package selectionSort;  import java.util.Scanner;  public class Test { 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();  } for(int i = 0 ; i < arr.length - 1 ; i++){ int maxIndex = i;  for(int j = i + 1; j < arr.length ; j++){ if(arr[maxIndex] < arr[j]){
                    maxIndex = j;  }
            } swap(arr,i,maxIndex);  } for (int i = arr.length - 1 ; i >= 0 ; i--){
            System.out.print(arr[i] + " ");  }
    } public static void swap(int[] arr,int i , int j){ int tmp = arr[i];  arr[i] = arr[j];  arr[j] = tmp;  }
}

编辑于 2023-07-05 10:28:45 回复(0)

C/C++

Yugina

#include<iostream>
using namespace std;
void selectSort(int *nums,int n)
{
for(int i=0;i<n-1;i++)
{
int min=i;
for(int j=i+1;j<n;j++)
{
if(nums[j]<nums[min])
min=j; //找出最小值
}
swap(nums[min],nums[i]);
}

}
int main()
{
int nums[1001];
int n;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>nums[i];
}
selectSort(nums, n);
for(int i=0;i<n;i++)
{
if(i != n - 1){
cout << nums[i] << " ";
} else {
cout << nums[i] << endl;
}
}
return 0;
}

发表于 2021-09-08 20:12:43 回复(0)

牛客902898874号

private void selectSort(int n, int[]arr) {
    for(int i=0; i<n-1; i++) {
        int minValue = arr[i];
        int minIndex = i;
        for(int j=i+1; j<n; j++) {
            if(minValue > arr[j]) {
                minIndex = j;
                minValue = arr[j];
            }
        }
        if(minIndex != i) {
            arr[minIndex] = arr[i];
            arr[i] = minValue;
        }
    }
}

发表于 2020-10-11 22:37:09 回复(0)

Elevenzou

#include<iostream>
using namespace std;
int nums[1005];
void selectSort(int *nums, int n);
int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> nums[i];
    }
    selectSort(nums, n);
    for(int i = 0; i < n; i++){
        if(i != n - 1){
            cout << nums[i] << " ";
        } else {
            cout << nums[i] << endl;
        }
    }
    system("pause");
    return 0;
}

void selectSort(int *nums, int n){
    for(int i = 0; i < n - 1; i++){
        int min = i;
        for(int j = i + 1; j < n; j++){
            if(nums[j] < nums[min]){
                min = j;
            }
        }
        swap(nums[i], nums[min]);
    }
}

发表于 2019-08-15 19:43:03 回复(0)