排序和算法总结 _JAVA_编程开发_程序员俱乐部

1. 基本思想：

　　每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。

2. 排序过程：

【示例】：

?? 初始关键字 [49 38 65 97 76 13 27 49]

第一趟排序后 13 ［38 65 97 76 49 27 49]

第二趟排序后 13 27 ［65 97 76 49 38 49]

第三趟排序后 13 27 38 [97 76 49 65 49]

第四趟排序后 13 27 38 49 [49 97 65 76]

第五趟排序后 13 27 38 49 49 [97 97 76]

第六趟排序后 13 27 38 49 49 76 [76 97]

第七趟排序后 13 27 38 49 49 76 76 [ 97]

最后排序结果 13 27 38 49 49 76 76 97

3.

void selectionSort(Type* arr,long len)

{

?? long i=0,j=0;/*iterator value*/

?? long maxPos;

?? assertF(arr!=NULL,"In InsertSort sort,arr is NULL\n");

?? for(i=len-1;i>=1;i--)

?? {

?? ?? ?? ??? maxPos=i;

?? ?? ?? ??? for(j=0;j<i;j++)

?? ?? ?? ?? ?? ?? if(arr[maxPos]<arr[j])maxPos=j;

?? ?? ?? ??? if(maxPos!=i)swapArrData(arr,maxPos,i);

?? }

}

选择排序法的第一层循环从起始元素开始选到倒数第二个元素,主要是在每次进 入的第二层循环之前,将外层循环的下标赋值给临时变量,接下来的第二层循环中,如果发现有比这个最小位置处的元素更小的元素,则将那个更小的元素的下标赋 给临时变量,最后,在二层循环退出后,如果临时变量改变,则说明,有比当前外层循环位置更小的元素,需要将这两个元素交换.

二.直接插入排序

插入排序（Insertion Sort）的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。

直接插入排序

　　直接插入排序（Straight Insertion Sort）：将一个记录插入到排好序的有序表中，从而得到一个新的、记录数增1的有序表。

直接插入排序算法