Selection sort导言:(取自Wiki)
In computer science, selection sort is a sorting algorithm, specifically an in-place comparison sort. It has O(n2) time complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is noted for its simplicity, and it has performance advantages over more complicated algorithms in certain situations, particularly where auxiliary memory is limited.
The algorithm divides the input list into two parts: the sublist of items already sorted, which is built up from left to right at the front (left) of the list, and the sublist of items remaining to be sorted that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.
我的翻译:(仅供参考:)
在计算机科学中,选择排序是一种特别的原位进行比较的排序算法。时间复杂度O(n2),造成了它在大量数据排序时候的低效,通常性能不如类似的插入排序。选择排序以简单著称,在某些情况下,相比更复杂的算法选择排序更具性能优势,特别是辅助内存有限的情况下。
该算法将输入列表分为两个部分:已经排序的子列表,是建立在列表以左为先的从左到右(左)的项依次排列的基础上的,剩下的待排序的子项列表占据了整个列表的其余部分。最初,已经排序的子列表是空的,未排序的子列表是整个输入列表。该算法通过寻找未排序子列表中最小(或最大,取决于排序顺序)的元素,与最左边的未排序的元素交换顺序(把它),并将子列表向右边界移动一个元素。
Here is an example of this sort algorithm sorting five elements:
| 64 25 12 22 11 // this is the initial, starting state of the array 11 25 12 22 64 // sorted sublist = {11} 11 12 25 22 64 // sorted sublist = {11, 12} 11 12 22 25 64 // sorted sublist = {11, 12, 22} 11 12 22 25 64 // sorted sublist = {11, 12, 22, 25} 11 12 22 25 64 // sorted sublist = {11, 12, 22, 25, 64} |
Selection sort can also be used on list structures that make add and remove efficient, such as a linked list. In this case it is more common to remove the minimum element from the remainder of the list, and then insert it at the end of the values sorted so far. For example:
(my translation:选择排序也可以被用在对于添加和删除元素高效的列表结构中，比如链表。在这种情况下，移动未排序列表中余下元素的最小值，将其插入到目前为止已排序列表的最后面就更为常用)
-------------------------------------------------------------------------------------------------------------------------------
Wiki中文版--选择排序解读:
选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。
-------------------------------------------------------------------------------------------------------------------------------
OK，通过上面的描述整个排序过程在逻辑上应该算是清晰了，下面就附一实例，用代码来实现。
问题描述:编写一个C程序，实现数据序列{2, 5, 6, 3, 7, 8, 0, 9, 12, 1}的选择排序，要求从大到小排列，并输出排序后的数列元素。
[分析] 该数据序列包含10个元素，因此可将它存放到一个含有11个单元的数组中，第0号单元可作为数据交换的临时空间。
程序清单
# include <stdio.h>void selectsort(int k[], int n) //选择排序{ int i, j, max; for(i=1; i<=n-1; i++) { max = i; for(j=i+1; j<=n; j++) //在后n-i+1个元素中找到最小的元素的位置 { if(k[j] > k[max]) max = j; //用max记录下最大元素的位置 } if(max != i) //如果最小的元素不位于后n-i+1个元素档第1个 { k[0] = k[max]; k[max] = k[i]; //元素的交换 k[i] = k[0]; } }}
int main(void){ int i; int a[11] = {-111, 2, 5, 6, 3, 7, 8, 0, 9, 12, 1}; //初始化序列，a[0]可任意置数 printf("The orginal data array is\n"); for(i=1; i<=10; i++) //显示原序列之中的元素 printf("%d ", a[i]); selectsort(a, 10); //执行选择排序 printf("\nThe result of selection sorting for the array is\n"); for(i=1; i<=10; i++) //输出排序后的结果 { printf("%d ", a[i]); } return 0;} |
在C-Free 5.0中的输出结果是:
The orginal data array is
2 5 6 3 7 8 0 9 12 1
The result of selection sorting for the array is
12 9 8 7 6 5 3 2 1 0 Press any key to continue . . .
我的实现方式:（贴出自己的实现方式只是为了保存当时的思路，用于反思自己和做一些总结，因为我觉得没有自己的思路，一味记忆书上的代码片段，效果不大，记忆不深刻，且效率不高。所以我是在了解了基本的编码思想，做出正确答案后（至少表面上测试正确），又看的书上给出的答案。）
# include <stdio.h># define true 1# define false 0typedef int bool;void selectsort(int a[], int length){ int max; int temp; int i; int j; bool flag = false; for(i=0; i<length-1; i++)
{ for(j=i+1,max=i; j<length; j++) { if(a[j] > a[max]) { max = j; flag = true;//对比程序清单，起初思路是没有flag语句的，转念一想，这样可能造成冗余（自己和自己交换），这种情况不应该出
现，因此使用了flag变量来判断是否需要交换变量。对比程序清单，不足之处在于多定义了变量，其实只需判断i和max是否相等即可得知是否需要交换变量。Tips：充分利用循环变量所提供的信息。 } } if(flag == true) { temp = a[max]; a[max] = a[i]; a[i] = temp; flag = false; } }}int main(void){ int a[10] = {2, 5, 6, 3, 7, 8, 0, 9, 12, 1}; selectsort(a, 10); int i; printf("选择排序后的顺序是:\n"); for(i=0; i<10; i++) { printf("%d ", a[i]); } return 0;} |
在C-Free 5.0中的输出结果是:选择排序后的顺序是:
12 9 8 7 6 5 3 2 1 0 Press any key to continue . . .
选择排序
