p的不同分割为若干个子序列然后分别进行插入排序得到若干组排好序的序列

缩小增量gap并对分割为的子序列进行插入排序最后一次的gap1即整个序列但此时已经基本有序对整个序列使用插入排序得到最终排好序的序列

{t1t2...tk}

时间复杂度最优复杂度O(nlogn)最差复杂度O(n2)平均复杂度O(nlogn)

空间复杂度O(1)

将未排序序列的所有元素分为若干组每个元素为一组将每组元素进行两两合并合并时按照从小到大或者从大到小对元素进行排序排序时比较每一组元素的头部即可重复此步骤直到最终只剩下一组数据则排序完成

2.算法复杂度

时间复杂度最优复杂度O(nlogn)最差复杂度O(nlogn)平均复杂度O(nlogn)

空间复杂度O(1)

R);System.out.println(Arrays.toString(a));}static

void

在未排序的序列中选择一个数作为基准一般选择序列的第一个数序列的最左侧和最右侧设置两个指针L和R

其中L从左往右移动R从右往左移动

首先R从右向左移动一位若指向的元素小于大于基准则将其移动到序列的最左边最右边然后L从左向右移动一位指向的元素与基准比较后执行相同操作

直到L与R移动到同一位置说明第一次排序完成此时相遇的位置就是基准元素的位置

接下来在基准的左右两边序列各选一个基准执行上述操作直到排序完成

2.算法复杂度

时间复杂度最优复杂度O(nlogn)最差复杂度O(nlogn)平均复杂度O(nlogn)

空间复杂度O(1)

t;}}//最后将基准为与i和j相等位置的数字交换arr[low]

arr[i];arr[i]