This page looks best with JavaScript enabled

常见排序算法

 ·  ☕ 3 min read · 👀... views

时间复杂度为O(n2) 空间复杂度O(1)

  • 冒泡排序

    (在0~N-1的序列上相邻两个元素比较大小,大的在后,小的在前,一趟下来,最大值放在位置N-1上,在0~N-2的序列上….)

  • 选择排序

    (在0~N-1的序列中选择最小值放在位置0上,在1~N-1上选择最小的值放在位置1上….)

  • 插入排序

    (位置0上的数与位置1上的数 进行比较 大的在后;位置2上的数记为a,与位置1上数进行比较,小的话,交换;再与位置0上数比较;接下来,位置K上的数,记为b,b依次与前面的数进行比较,如果小的话就交换;直到执行到位置为N-1的位置上的数,整个序列就有序了)

时间复杂度为O(N*logN)

  • 归并排序

    空间复杂度O(N)(在数组上的每一个数作为长度为1的有序区间,然后相邻的两个长度为1的区间进行合并,得到最大长度为2的有序区间,依次,2得4,4得8…最后直到数组中的数合并为一个有序地区间时,排序结束)

  • 快速排序

    空间复杂度O(logN)~O(N)(随机的在数组中选择一个数,小于等于这个数的数统一的放到这个数的左边,大于这个的统一放到右边;接下来左右两个部分分别递归的调用快速排序的过程,这样是的这个数组变得有序了)

  • 推排序

    空间复杂度O(1)(把数组中的N个数建为大小为N的大根堆<堆顶是最大元素>,堆顶元素与堆的最后一个元素交换,并脱离出来,作为数组的有序部分存在;对大小为N-1的堆进行大根堆的调整,在调整出N-1中的最大值与堆的最后一位交换位置,放在有序部分;这样堆的大小依次减1,有序部分会依次加一,直到堆的大小变为1时,整个数组变得有序)

  • 希尔排序

    (改进的 空间复杂度O(1)插入排序<步长为1>,改为步长为n的排序算法,步长依次减小,直到回到<经典的插入排序>步长为一,希尔算法的优劣取决于步长的选择)

时间复杂度为O(N) 空间复杂度O(M) M:划分的桶的数量

  • 计数排序
  • 基数排序

排序的稳定性:

  • 稳定:冒泡 插入 归并 计数 基数 桶排序
  • 不稳定: 选择(1 2 2 2) 快排(4 3 3 3 5) 希尔(5 1 1 5) 堆排序(5 5 5 )

注意点:
1.工程上的排序是运用了综合排序
2.但元素比较小(数组较小),插入排序
3.数组较大时,快速排序或其他O(N*logN)的排序

几乎有序的数组(元素移动距离K远远小于数组的长度N),用什么排序
解:冒泡,选择与原始序列无关,时间复杂度O(N2);插入最大移动元素的距离不会超过K,所以,时间复杂度不会超过O(NK);快排,归并与原始数据顺序无关,时间复杂的为O(NlogN)
答:改进后的堆排序(小根堆)时间复杂度O(N*logK)

Share on

睡沙发の沙皮狗
WRITTEN BY
睡沙发の沙皮狗
👨‍💻 Backend Developer/📚 Learner/🚀 Opensource enthusiast

 

What's on this Page