1.直插排序
思想:
每一趟,对于待排序元素a[i],该元素前面的子序列已有序;在有序序列中从后往前查找其插入位置,一边比较一边移动。直至找到插入位置,插入该元素;一共n-1趟。
举例:
待排序序列: 5 8 4 12 9
第一趟: 5 8 4 12 9
第二趟: 4 5 8 12 9
第三趟: 4 5 8 12 9
第四趟: 4 5 8 9 12
代码:
public static void insertSort(int a[]){
int n=a.length;
int toSort;//存储待排序元素
for (int i=1;i<n;i++){
//n-1趟
if(a[i]<a[i-1]){
//若>=,无需移动插入
toSort=a[i];
int j;
for (j=i-1; j>=0;j--) {
//从后往前查找插入位置
if (toSort < a[j])//边比较
a[j + 1] = a[j];//边移动
else break;
}
a[j+1]=toSort;//插入到插入位置
}
}
}
说明:
2.希尔排序
思想:
先将待排序表分割成若干个形如a[i,i+d,i+2d,…,i+kd]的子表 ,分别进行直插排序;当整个表呈现“基本有序”时,再对全体进行一次直插排序。
存在一个增量序列di ,d1=n/2 , di+1=di/2 ,并且最后一个增量1 .
举例:
待排序序列 di={5,3,1}:50 26 38 80 70 90 8 30 40 20
第一趟(增量5): 50 8 30 40 20 90 26 38 80 70
第二趟(增量3): 26 8 30 40 20 80 50 38 90 70
第三趟(增量1): 8 20 26 30 38 40 50 70 80 90
代码:
public static void shellSort(int a[]){
int n=a.length;
int toSort;//存储待排序元素
for (int d=n/2 ;d>=1 ;d=d/2)//增量变化
for (int i=d;i<n ;i++){
if(a[i]<a[i-d]){
toSort=a[i];
int j;
for (j=i-d ;j>=0 ; j-=d){
if(toSort<a[j]) a[j+d]=a[j];
else break;
}
a[j+d]=toSort;
}
}
}
说明:
3.冒泡排序
思想:
每一趟,从后往前,两两比较,逆则交换;每趟结果让最小元素到达最终位置,若该趟没有发生交换,说明表已经有序。最多n-1趟。
举例:
待排序序列:5 8 4 12 9
第一趟: 4 5 8 9 12
第二趟: 4 5 8 9 12
代码:
public static void bubbleSort(int a[]){
boolean flag;//标志某趟是否交换过
int n=a.length;
for (int i