1、基本思想:
在要排序的一组数中,选出最小的一个数与第一个位置的数交换;然后在剩下的数当中再找最小的与第二个位置的数交换,如此循环到倒数第二个数和最后一个数比较为止。
2、实例
3、算法实现
public static void selectSort(int[] numbers)
{
int size=numbers.length; //数组长度
int temp=0 ; //中间变量
for(int i=0 ; i < size ; i++)
{
int k=i; //待确定的位置
//选择出应该在第i个位置的数
for(int j=size -1 ; j > i ; j--)
{
if(numbers[j] < numbers[k])
{
k=j;
}
}
//交换两个数
temp=numbers[i];
numbers[i]=numbers[k];
numbers[k]=temp;
}
}
二、插入排序
1、基本思想:每步将一个待排序的记录,按其顺序码大小插入到前面已经排序的字序列的合适位置(从后向前找到合适位置后),直到全部插入排序完为止。
2、实例
3、算法实现
public static void insertSort(int[] numbers)
{
int size=numbers.length;
int temp=0 ;
int j=0;
for(int i=0 ; i < size ; i++)
{
temp=numbers[i];
//假如temp比前面的值小,则将前面的值后移
for(j=i ; j > 0 && temp < numbers[j-1] ; j --)
{
numbers[j]=numbers[j-1];
}
numbers[j]=temp;
}
}
4、效率:
时间复杂度:O(n^2).
三、希尔算法
1、基本思想:
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行依次直接插入排序。
2、操作方法:
选择一个增量序列t1,t2,…,tk,其中ti>tj,tk=1;
按增量序列个数k,对序列进行k 趟排序;
每趟排序,根据对应的增量ti,将待排序列分割成若干长度为m 的子序列,分别对各子表进行直接插入排序。仅增量因子为1 时,整个序列作为一个表来处理,表长度即为整个序列的长度。
希尔排序的示例:
3、算法实现:
public static void shellSort(int[] data)
{
int j=0;
int temp=0;
//每次将步长缩短为原来的一半
for (int increment=data.length / 2; increment > 0; increment /=2)
{
for (int i=increment; i < data.length; i++)
{
temp=data[i];
for (j=i; j >=increment; j -=increment)
{
if(temp > data[j - increment])//如想从小到大排只需修改这里
{
data[j]=data[j - increment];
}
else
{
break;
}
}
data[j]=temp;
}