排序

排序的概念，排序算法的原理和时间复杂度

排序

• 排序(将一个记录,重新排序成一个按关键字有序的序列)
• 算法(插入排序）
  • 插入 O(n^2) 对未排序的数据，在已排序序列中从后向前扫描，找到相应位置并插入
  • 折半插入 O(n^2)不断的依次将元素插入前面已排序好的序列中
  • 希尔 缩小增量法O(n^2)每一轮按照事先决定的间隔进行插入排序，间隔依次缩小，最后是1次
• 算法(交换排序)
  • 冒泡 O(n^2) 从无序区透过交换找出最大元素放到有序区前端
  • 快速O(n^2)在区间中随机选一个元素做基准,将小于基准的元素放在基数前,大于基数放后面,在分别进行排序
• 算法( 选择排序)
  • 简单选择O(n^2) 在无序区找一个最小的元素跟在有序区后面。 跟冒泡相反
  • 堆排序 O(nlogn) 从最大堆把根卸出来放在有序区之前,再恢复堆
• 归并
  • 归并排序 O(nlog^2n)把数据分为两段,从两段中逐个移入新数据末尾
• 基数
  • 基数排序O(kn)将所有待比较数值统一成一样的数字长度,从最低位排序到最高位