交换排序(冒泡排序~快速排序~)+插入排序(直接插入排序~希尔排序~)
一、冒泡排序
1、基本概念
依次比较相邻的两个数,将小数放在前面,大数放在后面。
第一趟:首先比较第1个数和第2个数,将小数放前,大数放后;然后比较第2个数和第3个数,将小数放前,大数放后;如此继续,直至比较最后两个数,将小数放前,大数放后;至此第一趟结束,使得最后一个数字是最大的了!
第二趟:仍从第一对数开始比较,将小数放前,大数放后,一直比较到倒数第二个数字,(倒数第一的位置已经是最大的了),第二趟结束,在倒数第二个位置上得到了一个新的最大的数字(整个数组当中第二大数字)!
如此过程,重复进行下去,直达最终完成排序。
2、实现思路
使用二重循环实现,外变量设为i,内部变量设为j。假如有n个数据要进行排序,则外循环重复n-1次,内部循环依次重复n-1,n-2,......1次,外部循环控制执行的趟数,内部循环控制比较的数字,每次比较的两个数字都是与j有关,分别可以用a[j]和a[j+1]来识别,i的值依次为1,2,......,n-1,对于每一个i,j的值依次为1,2,......,n-i。
舞蹈之冒泡排序:http://v.youku.com/v_show/id_XMzMyOTAyMzQ0.html?from = s1.8-1-1.2
时间复杂度:最坏情况:O(n ^ 2)、最好情况:O(n)
空间复杂度:O(1)
代码演示:
/*
* 冒泡排序
*/
public static<T> void Swap(T [] arr,int i,int j){
T temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
public static<T extends Comparable<T>> void ButtleSort(T[] arr){
int len=arr.length;
for(int i=0;i<len;i++){
for(int j=0;j<len-i-1;j++){
if(arr[j].compareTo(arr[j+1])>0){
Swap(arr,j,j+1);
}
}
}
}
二、快速排序(对冒泡排序的一种改进)
1、算法思想
首先从数组当中选择出一个数字作为基准数字;分区过程,将比基准大的数字全部放在基准的右边,比基准小的数字放在基准的左边;再对左右区间重复第二步,直到各区间只有一个数字为止!
2、时间复杂度:O(n * logn)
最坏:O(n ^ 2)
空间复杂度:O(n * logn)
舞蹈之快速排序:http://v.youku.com/v_show/id_XMzMyODk4NTQ4.html?from = s1.8-1-1.2
代码演示:
/*
* 快速排序
*/
public static<T extends Comparable<T>> int quickSort(T[] arr,int low,int high){
T temp=arr[low]; //将数组中的第一个数字作为基准
while(low<high){
while(low<high && arr[high].compareTo(temp)>=0){
high--;
}
arr[low]=arr[high]; //找到比基准小的数字挪动到左边
while(low<high && arr[low].compareTo(temp)<0){
low++;
}
arr[high]=arr[low]; //找到比基准大的数字挪动到右边
}
arr[low]=temp; //最后将基准放到空出来的位置
return low; //返回基准的最终位置
}
public static<T extends Comparable<T>> void quick(T[] arr,int low,int high){
if(low < high){//将数组一分为二,进行递归调用
int pos=quickSort(arr,low,high);
quick(arr,low,pos-1);
quick(arr,pos+1,high);
}
}
三、直接插入排序
1、算法思想
直接插入排序算法的思想是将一个记录插入到已经排好序的表中,从而得到一个新的、记录数增1的有序表。对于给定的一组记录,初始时假定第一个数据自成一个有序序列,其余记录为无序的序列。接着从第二个记录开始,按照记录的大小依次将当前处理的记录插入到其之前的有序序列中,直到最后一个记录插入到有序的序列中为止。
2、算法步骤
首先从第一个元素开始,该元素被假定为有序的;取出下一个元素,在已经排好序的数组中从前往后遍历;如果该元素(已排序)大于新元素,则将该元素移到下一个位置;重复上一步,直到找到已排序的元素小于或者大于新元素的位置;将新元素插入到该位置;重复进行下去。
舞蹈之插入排序:http://v.youku.com/v_show/id_XMzMyODk3NjI4.html?from = s1.8-1-1.2
时间复杂度:最好的情况:O(n)、最坏的情况:O(n ^ 2)
空间复杂度:O(1)
代码演示:
/*
* 插入排序
*/
public static<T extends Comparable<T>> void insertSort(T[] arr){
int i,j;
T NoteNumber;//要插入的数据
for(i=1;i<arr.length;i++){
NoteNumber=arr[i];//循环将数组中的数据作为要插入的新元素
j=i-1;
while(j>=0 && arr[j].compareTo(NoteNumber)>0){//插入的数据小于第j个元素,将数据进行向后挪动
arr[j+1]=arr[j];
j--;
}
arr[j+1]=NoteNumber;//直到插入的数据小于第j个元素,进行插入!
}
}
四、希尔排序
1、算法思想
希尔排序是一种插入排序,又被称为缩小增量排序。希尔排序的算法思想就是:将数据进行分组,然后对每一组数据进行排序,在每一组数据有序后,就可以对所有的分组利用插入排序进行最后一次的排序,这样可以达到减少交换的次数,达到加速的目的。
2、算法演练
假定待排序的数组有10条记录,其分别为40、38、65、97、76、13、27、49、55、4。
步长取值分别为5,3,1
时间复杂度:最好的情况:O(n) 最坏的情况下:O(n ^ 2)
空间复杂度:O(1)
舞蹈之希尔排序:http://v.youku.com/v_show/id_XMzMyODk5MzI4.html?from = s1.8-1-1.2
排序过程如下:
代码演示:
/*
* 希尔排序
*/
public static<T extends Comparable<T>> void shellSort(T[] arr){
T temp;
int step=arr.length;
while(true){
step=step/2; //默认步长为数组的长度除以2
for(int i=0;i<step;i++){//确定分组数
for(int j=i+step;j<arr.length;j=j+step){//对分组的数据进行直接插入排序
temp=arr[j];
int k=0;
for(k=j-step;k>=0;k=k-step){
if(arr[k].compareTo(temp)>0){
arr[k+step]=arr[k];
}else{
break;
}
}
arr[k+step]=temp;
}
}
if(step==1){
break;
}
}