插入排序和冒泡排序都比较简单，但是时间复杂度有点高。
首先是冒泡排序，是通过相邻的两个数字进行比较，每一趟之后，待排序的部分的最大值将会到后面去，这样就可以每一趟确定一个数字，在n-1趟之后，就完成了排序工作。
如：2 32 43 5 21
第一趟：2 32 43 5 21 2 32 43 5 21 2 32 5 43 21 2 32 5 21 43
第二趟：2 32 5 21 43 2 5 32 21 43 2 5 21 32 43
第三趟：2 5 21 32 43 2 5 21 32 43
第四趟：2 5 21 32 43
可以看到其实每一趟是待排序列或子序列下沉的过程。
时间复杂度是T(N)=N-1+N-2+......+1=o(N^2)
java实现
public static void bubble_sort(int [] arr){
int tem=0;
for(int i=0;i<arr.length-1;i++){
for(int j=0;j<arr.length-i-1,j++){
if(arr[j]>arr[j+1]){
tem=arr[j];
arr[j]=arr[j+1];
arr[j+1]=tem;
}
}
}
}
插入排序，插入排序的每一趟的结果是将一个待排的数正确的插入到已经排序好的序列中。例如，待排序列：8 6 3 9 2
第一趟 6 8
第二趟 3 6 8
第三趟 3 6 8 9
第四趟 2 3 6 8 9
所以，这种插入排序的需要进行N-1次的遍历，时间复杂度是T（N）=1+2+.......+N-1=o(N^2)
在实现的过程中，为了减少空间的占用，整个排序只在一个数组内完成，数据的第一个数默认为是有序的，然后从数组的第二个数开始，和前面的已经排序好的数字进行比较，在每一次比较的过程中，如果发现待排的数字与比较的数字比更小，说明这个待排数字的正确位置是在这个比较数字的前面，然后将这个数右移一位，然后待排数再和前面一个数比较，如果发现更小，继续将这个右移。这样等于是将已经比较过的这些数整体右移的一个位置，而由于待排的数字刚好是在已经排序好的序列的后面，所以这样做是有位置的，同时如果在比较的过程中发现了待排数字和比较数字相比更大，说明这个待排数字是在这个已派数字的后面，而与之前的已排数字相比，这个又比前一个已经右移一位的已排数字的位置更小（不然也不会继续比较前面的一个），所以这个待排数字的正确位置就确定下来了，就是之前这个右移一位所空下来的位置的数原先所在数的位置。
java实现
public static void insert_sort(int [] arr){
for(int i=1;i<=arr.length-1;i++){
int j;
int tem=arr[i];//保存待排的一个备份，因为右移的时候原来的值会被前面的值覆盖
for(j=i-1;j>=0&&arr[j]>=tem;j--){
arr[j+1]=arr[j];
}
arr[j+1]=tem;
}
}
这种也称为直接的插入排序，但是这种方法每一次待排的数字在找到其正确位置时，需要一个一个顺序的和原来的序列的值从头到尾或者从尾到头进行比较，还有一种优化的插入排序是，在寻找待排数字在已经排好的序列正确位置的时候，为了减少比较次数，采用二分查找的方式，选择已派序列中间的数和待排数字进行比较，如果待排数字更大，则其应该位于这个中间数字到尾部的区域，继续二分，直到可以确定位置以后，将序列整体右移1位，插入。
public static void(int [] arr){
for(int i=1;i<=arr.length-1;i++){
int left=0;
int temp=arr[i];
int right=i-1;
int mid;
while(left<=right){ //二分查找位置，
mid=(left+right)/2;
if(arr[mid]>=arr[i])
right=mid-1;
else
left=mid+1;
} //退出循环的条件的前一次是，left和right指向一个元素，然后比较它和待排元素的大小，如果待排更大，则left会变得更 大，待排应该插在其右边，如果待排更小，则right会变得更小，待排应该插到其左边。不管如何，都是查到最终left的左 边
for(int j=i-1;j>=left;j--){
arr[j+1]=arr[j];
}
arr[left]=temp;
}
}
网友评论