算法简析之直接选择排序

发表于   |  

简析

概念

直接选择排序（Select sort） 每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子文件的最后，直到全部记录排序完毕。

原理

  1. 初始时，数组全为无序区为a[0..n-1]。令i=0

  2. 在无序区a[i…n-1]中选取一个最小的元素，将其与a[i]交换。交换之后a[0…i]就形成了一个有序区。

  3. i++并重复第二步直到i==n-1。排序完成。

范例（java）

概念代码

 public static void main(String[] args) {
    int arr[] = {23, 44, 56, 21, 32, 55, 74, 13};
    int count = arr.length;
    int i, j, min;
    for (i = 0; i < count; i++) {
        min = i;
        for (j = i + 1; j < count; j++) {
            if (arr[j] < arr[min]) {//找最小元素的位置
                min = j;
            }
        }

        int temp = arr[i];
        arr[i] = arr[min];
        arr[min] = temp;

        System.out.print("第" + (i + 1) + "次排序结果：");
        for (int anArr : arr) {
            System.out.print(anArr + "\t");
        }
        System.out.println("");
    }

    System.out.print("最终排序结果：");
    for (int anArr : arr) {
        System.out.print(anArr + "\t");
    }
}

1
2
3
4
5
6
7
8
9
第1次排序结果：13	44	56	21	32	55	74	23	
第2次排序结果：13	21	56	44	32	55	74	23	
第3次排序结果：13	21	23	44	32	55	74	56	
第4次排序结果：13	21	23	32	44	55	74	56	
第5次排序结果：13	21	23	32	44	55	74	56	
第6次排序结果：13	21	23	32	44	55	74	56	
第7次排序结果：13	21	23	32	44	55	56	74	
第8次排序结果：13	21	23	32	44	55	56	74	
最终排序结果：13	21	23	32	44	55	56	74