经典的排序算法，选择排序

0准备

 1//建立一个排序用的顺序表结构L
 2#define MAXSIZE 9
 3typedef struct SqList
 4{
 5    int r[MAXSIZE];
 6    int length;
 7}SqList;
 8/*排序的交换函数*/
 9void swap(SqList* L,int i,int j)
10{
11    int temp = L->r[i];
12    L->r[i] = L->r[j];
13    L->r[j] = temp;
14}

1选择排序(SelectSort)

选择排序的思想其实和冒泡排序有点类似，选择排序可以看成冒泡排序的优化。

  • 首先，找到数组中最大（小）的那个元素：
  • 其次，将它和数组的第一个元素交换位置（如果第一个元素就是最大（小）元素那么它就和自己交换)
  • 再次，在剩下的元素中找到最大（小）的元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序

这种方法叫做选择排序，因为它在不断地选择刺余元素之中的最大（小）者。

C的版本

 1void SelectSort(SqList *L)
 2{
 3   int i,j;
 4   for(i = 0; i < L->length - 1; i++)
 5   {
 6       int min = i;
 7       for(j = i + 1; j < L->length; j++)
 8       {
 9           if(L->r[j] < L->r[min])
10           {
11               min = j;
12           }
13       }
14       if(i != min)/**需要判断i和min，减少交换次数*/
15       {
16           swap(L, i, min);
17       }
18   }
19}

i = 0的时候

i = 1的时候

i = 2的时候

i = 3的时候

i = 4的时候

i = 5的时候

i = 6的时候

i = 7的时候

Java版本

 1public int[] SelectSort(int[] nums){
 2    if(0 == nums.length)
 3    {
 4        return nums;
 5    }
 6    for(int i = 0; i < nums.length; i++)
 7    {
 8        //最小数的下标。每个循环开始总假设第一个数最小
 9        int minIndex = i;
10        for(int j = i; j < nums.length; j++)
11        {
12            if(nums[j] < nums[minIndex])
13            {
14                //保存最小值的索引
15                minIndex = j;
16            }
17        }
18        System.out.Println("最小数为:" + nums[minIndex]);
19        //交换最小数和i当前所指的下标
20        int tmp = nums[minIndex];
21        nums[minIndex] = nums[i];
22        nums[i] = tmp;
23    }
24    return nums;
25}