直接插入排序
适合原本基本有序的序列。
时间复杂度O(n^2)。
插入排序详细步骤
代码
public class Main {
public static void main(String args[]) {
int[] arr= {3,5,1};
insertSort(arr);
for(int num:arr) {
System.out.print(num);
}
}
public static void insertSort(int[] arr) {
for(int i=1;i<arr.length;++i) {
for(int j=i-1;j>=0&&arr[j]>arr[j+1];--j) {
swap(arr,j,j+1);
}
}
}
private static void swap(int[] arr, int i, int j) {//
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
希尔排序
- 设置初始增量，增量慢慢变为原来的1/2，保证增量条约对应的一组组数内部有序，采用直接插入排序。
- 是改进的插入排序，就是为了使数组基本有序：指小的基本在前面，中的基本在中间，大的基本在后面。(区分于局部有序)。这样可以大大减少交换次数。
- 时间复杂度与增量的选取有关，平均O(nlogn)。
希尔排序详细步骤
- 也称为缩小增量排序。是直接插入排序的改进版本。希尔排序是非稳定排序算法。
- 基本思想：将待排序列按增量划分为若干组，在每一组内进行插入排序。不断减小增量，并在组内插入排序，直至增量减小为1。
- 优劣：
- 不需要大量的辅助空间，和归并排序一样容易实现。
- 希尔排序的时间复杂度与增量序列的选取有关，例如希尔增量时间复杂度为O(n²)，而Hibbard增量的希尔排序的时间复杂度为O()，希尔排序时间复杂度的下界是n*log2n。
3. 希尔排序没有快速排序算法快 O(n(logn))，因此中等大小规模表现良好，对规模非常大的数据排序不是最优选择。
4. 希尔算法在最坏的情况下和平均情况下执行效率相差不是很多，而快速排序在最坏的情况下执行的效率会非常差。
代码
public class Main {
public static void main(String args[]) {
int[] arr= {3,5,1};
shellSort(arr);
for(int num:arr) {
System.out.print(num);
}
}
public static void shellSort(int arr[]) {
int len = arr.length;
for(int gap=len/2; gap>=1; gap=gap/2){
for(int i=gap+1; i<len; i++){
for(int j=i-gap; j>=0&&arr[j]>arr[j+gap]; j=j-gap){
swap(arr,j,j+gap);
}
}
}
}
private static void swap(int[] arr, int i, int j) {
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}