Question

数据结构快速排序和基数排序

Answer 1

问：数据结构快速排序和基数排序

答：您好亲，很高兴为您解答。.基数排序（桶排序）：低位优先，所有数据从低位开始，一次放入到10个桶内，再次从桶里取出，直到完全有序。快速排序：每次找基准值的位置，以基准线为分界线，左边的值全部比基准值小，而右边的值肯定比基准值大。规则：从右向左找比基准值小的数据放到左边，找到后放到左边，从左向右找比基准值大的数据，找到后放到右边，重复上面的操作，直到left=right，循环退出，再将基准值放到arr[left]或者arr[right]。

答：您好亲，很高兴为您解答。#include #include #include //八大排序 排序分为升序和降序 我们默认使用升序//算法的描述 算法的实现 算法的评价（时间复杂度，空间复杂度，稳定性）//什么是稳定性：如果排序前A在A`的前面，排序之后A孩子A`的前面，则排序算法稳定//如何判断其稳定性：看算法中是否存在跳跃交换//第一个排序算法：直接插入排序：每次从待排序队列中取一个值，放到已排序好的队列，再次保持有序，重复这样的动作，直到把待排序队列中的值全部取完 时间复杂度O（n^2） 空间复杂度O（1） 稳定的//第二个排序算法：希尔排序（缩小增量排序）：是一个特殊的直接插入排序，相当于多次调用直接插入排序，每一次的增量保持互素，并且最后一个增量一定位1，为1才能保证其完全有序 时间复杂度O(n^1.3~1.5) 空间复杂度O(1) 不稳定//第三个排序算法：冒泡排序（沉石排序）：两两比较，大的向后挪动，小的向前 时间复杂度O（n^2） 空间复杂度O（1） 稳定的（不存在跳跃交换）//第四个排序算法：二路归并排序（非递归形式）：两两合并成一个组，当合并后的组能容纳arr所有值的时候，则退出，因为此时已经组内完全有序 时间复杂度O(nlogn) 空间复杂度O（nlogn） 稳定//第五个排序算法：简单选择排序：每一次将待排序序列中最小值和待排序序列中第一个值进行交换 直到完全有序即可 时间复杂度O（n^2） 空间复杂度O（1） 不稳定//第六个排序算法：堆排序：将一维数组臆想成一个完全二叉树，再将其调整为大顶堆，再将根节点和尾节点进行交换，再次进行调整，这样循环往复，直至将其调整为完全有序 时间复杂度O（nlogn） 空间复杂度O（1） 不稳定 //第七个排序算法：基数排序（桶排序）：低位优先，所有数据从低位开始，一次放入到10个桶内，再次从桶里取出，直到完全有序。时间复杂度O(dn),空间复杂度O(n)//第八个排序算法：快速排序：从右向左找比基准值小的数据放到左边，找到后放到左边，从左向右找比基准值大的数据，找到后放到右边，重复上面的操作，直到left=right，循环退出，再将基准值放到arr[left]或者arr[right