选择排序(Select_Sort)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

void select_sort(int a[],int n)
{
    for(int i=0;i<n-1;i++)//i为已排序序列的末尾
    {
        for(int j=i+1;j<n;j++){
            if(a[j]<a[i]){
                int temp=a[i];
                a[i]=a[j];
                a[j]=temp;
            }
        }
            
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void select_sort(int a[],int n)
{
    int min;
    for(int i=0;i<n-1;i++)//i为已排序序列的末尾
    {
        min=i;
        for(int j=i+1;j<n;j++)//未排序序列
            if(a[j]<a[min])//找出未排序序列中的最小值
                min=j;
        if(min!=i)
            swap(a[i],a[min]);//放到已排序序列的末尾，该操作很有可能把稳定性打乱，所以选择排序是不稳定的排序算法
    }
}
 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//选择排序
public class SelectionSort {
    public static void main(String[] args) {
        int[] arr={1,3,2,45,65,33,12};
        System.out.println("交换之前：");
        for(int num:arr){
            System.out.print(num+" ");
        }        
        //选择排序的优化
        for(int i = 0; i < arr.length - 1; i++) {// 做第i趟排序
            int k = i;
            for(int j = k + 1; j < arr.length; j++){// 选最小的记录
                if(arr[j] < arr[k]){ 
                    k = j; //记下目前找到的最小值所在的位置
                }
            }
            //在内层循环结束，也就是找到本轮循环的最小的数以后，再进行交换
            if(i != k){  //交换a[i]和a[k]
                int temp = arr[i];
                arr[i] = arr[k];
                arr[k] = temp;
            }    
        }
        System.out.println();
        System.out.println("交换后：");
        for(int num:arr){
            System.out.print(num+" ");
        }
    }

}