排序算法可以分为内部排序和外部排序:
通常人们整理桥牌的方法是一张一张的来,将每一张牌插入到其他已经有序的牌中的适当位置。在计算机的实现中,为了要给插入的元素腾出空间,我们需要将其余所有元素在插入之前都向右移动一位。
一般来说,插入排序都采用in-place在数组上实现。具体算法描述如下:
public static void main(String[] args) {
int arr[] = {7, 5, 3, 2, 4};
//插入排序
for (int i = 1; i < arr.length; i++) {
//外层循环,从第二个开始比较
for (int j = i; j > 0; j--) {
//内存循环,与前面排好序的数据比较,如果后面的数据小于前面的则交换
if (arr[j] < arr[j - 1]) {
int temp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = temp;
} else {
//如果不小于,说明插入完毕,退出内层循环
break;
}
}
}
}
时间复杂度:
插入排序所需的时间取决于输入元素的初始顺序。例如,对一个很大且其中的元素已经有序(或接近有序)的数组进行排序将会比随机顺序的数组或是逆序数组进行排序要快得多。
public static void main(String[] args) {
int arr[] = {8, 5, 3, 2, 4};
//冒泡
for (int i = 0; i < arr.length; i++) {
//外层循环,遍历次数
for (int j = 0; j < arr.length - i - 1; j++) {
//内层循环,升序(如果前一个值比后一个值大,则交换)
//内层循环一次,获取一个最大值
if (arr[j] > arr[j + 1]) {
int temp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = temp;
}
}
}
}
排序过程:
时间复杂度:
public void sort3(int arr[]) {
for(int i = 0; i < arr.length; i++){
int min = arr[0];
int index = i;
for(int j = i + 1; j <arr.length; j++){
if(min > arr[j]){
index = j;
min = arr[j];
}
}
int temp = arr[i];
arr[i] = min;
arr[index] = temp;
}
System.out.println("选择排序,排序后--------------------");
}
排序过程:
希尔排序也是一种插入排序,它是简单插入排序经过改进之后的一个更高效的版本,也称为缩小增量排序,同时该算法是冲破O(n2)的第一批算法之一。
看下希尔排序的基本步骤:
public static void swap(int []arr,int a,int b){
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
/**
* 希尔排序 针对有序序列在插入时采用交换法
* @param arr
*/
public static void sort(int []arr){
//增量gap,并逐步缩小增量
for(int gap=arr.length/2;gap>0;gap/=2){
//从第gap个元素,逐个对其所在组进行直接插入排序操作
for(int i=gap;i<arr.length;i++){
int j = i;
while(j-gap>=0 && arr[j]<arr[j-gap]){
//插入排序采用交换法
swap(arr,j,j-gap);
j-=gap;
}
}
}
}
排序过程: