潍坊高端网站开发,做网站毕业设计能过吗,90设计网官网首页,厂房设计装修公司排序的其他相关知识点和源码分享可以参考之前的博客#xff1a;
《数据结构与算法基础-学习-30-插入排序之直接插入排序、二分插入排序、希尔排序》 一、交换排序基本思想
两两比较#xff0c;如果发生逆序则交换位置#xff0c;直到所有数据记录都排好序为止。 二、冒…排序的其他相关知识点和源码分享可以参考之前的博客
《数据结构与算法基础-学习-30-插入排序之直接插入排序、二分插入排序、希尔排序》 一、交换排序基本思想
两两比较如果发生逆序则交换位置直到所有数据记录都排好序为止。 二、冒泡排序基本思想
每趟不断地将数据记录两两比较并按照升序或降序规则进行交换。 三、冒泡排序算法实现思路 这里的哨兵起的是临时变量的作用在交换元素时使用。
我们还是以升序为例。 1、第一趟
一共有7个元素需要比较6次因为没有8号位。
11小于2不要交换继续 22小于8不要交换继续 38大于5需要交换继续 48大于4需要交换继续
58大于6需要交换继续 68大于3需要交换6次比较完已经把最大值8放到了最后一位那下一趟比较时就不需要比较8了。 2、第二趟
一共有6个元素需要比较总共需要比较5次因为7号位的8已经完成排序。
11小于2不要交换继续 22小于5不要交换继续 35大于4需要交换继续 45小于6不要需要交换继续 56大于3需要交换5次比较完已经把最大值6放到了最后一位那下一趟比较时就不需要比较68了。 3、第三趟
一共有5个元素需要比较总共需要比较4次因为6和8已经完成排序。
规律都知道了我们这就快进一些跳过了一些对比步骤。
12345都是升序不需要移动。
15大于3需要交换4次比较完已经把最大值5放到了最后一位那下一趟比较时就不需要比较568了。 4、第四趟
一共有4个元素需要比较总共需要比较4次因为56和8已经完成排序。
规律都知道了我们这就快进一些跳过了一些对比步骤。
124都是升序不需要移动。
14大于3需要交换3次比较完已经把最大值4放到了最后一位那下一趟比较时就不需要比较4568了。 5、第五趟
一共有4个元素需要比较总共需要比较3次因为456和8已经完成排序。
1234就是升序的没有交换元素说明序列已经是有序的排序完成。 四、冒泡排序算法源码
1、BubbleSortSentrySqQueue
Status BubbleSortSentrySqQueue(SqQueue* Queue)
{JudgeAllNullPointer(Queue);if (Queue-Flag ! INT_TYPE_FLAG){return FailFlag;}int* Array (int*)(Queue-Data);int SwapFlag 0;QueueLenType i;QueueLenType j;for (i 1; i Queue-SqQueueLen - 1; i)//长度n比较n - 1趟。{SwapFlag 0;for (j 1; j Queue-SqQueueLen - i; j)//每趟比较 n - 第i趟 次。找个测试数据更明显好理解{if (Array[j] Array[j 1]){Array[0] Array[j 1];Array[j 1] Array[j];Array[j] Array[0];SwapFlag 1;}}if (SwapFlag 0)//如果某一趟不需要进行交换说明所有元素都是有序的退出循环。{break;}}LogFormat(Debug,Bubble Sort SqQueue OK.\n);return SuccessFlag;
} 五、冒泡排序算法效率
情况时间复杂度是否稳定最好O(n)稳定最坏O(n^2)平均O(n^2)
最好的情况例如冒泡升序排序数据是升序排列的只需要比较n-1次即可不需要移动元素。
最坏的情况例如冒泡升序排序数据是降序排列的
1需要比较次数为
长度为n的序列需要比较n-1次每次少比一次直到1为止可以使用等差求和公式:
((n - 1) 1) * (n - 1) / 2 n^2 - n/ 2
2需要移动次数为
每比较一次需要交换一次交换需要临时变量存放一共需要三步所以乘以3。 Array[0] Array[j 1];Array[j 1] Array[j];Array[j] Array[0];
n^2 - n/ 2 * 3。 六、冒泡排序Linux环境编译测试
[gbaseczg2 Sort]$ time ./TestSort
2023-9-1--[ Debug ]--Init SqQueue OK
2023-9-1--[ Debug ]--Enter SqQueue OK
2023-9-1--[ Debug ]--Enter SqQueue OK
2023-9-1--[ Debug ]--Enter SqQueue OK
2023-9-1--[ Debug ]--Enter SqQueue OK
2023-9-1--[ Debug ]--Enter SqQueue OK
2023-9-1--[ Debug ]--Enter SqQueue OK
2023-9-1--[ Debug ]--Enter SqQueue OK
2023-9-1--[ Debug ]--Enter SqQueue OK
2023-9-1--[ Debug ]--Enter SqQueue OK
2023-9-1--[ Debug ]--Enter SqQueue OK
2023-9-1--[ Debug ]--Enter SqQueue OK
2023-9-1--[ Debug ]--SqQueue Data :
Data : [ 0 ,10 ,9 ,8 ,7 ,6 ,5 ,4 ,3 ,2 ,1 ]
FrontIndex : 0
RearIndex : 0
SqQueueLen : 11
SqQueueMaxLen : 11
Flag : INT_TYPE_FLAG
2023-9-1--[ Debug ]--Bubble Sort SqQueue OK.
2023-9-1--[ Info ]--Sort Function Elapsed Time : 0 s
2023-9-1--[ Info ]--SqQueue Data :
Data : [ 1 ,1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ,10 ]
FrontIndex : 0
RearIndex : 0
SqQueueLen : 11
SqQueueMaxLen : 11
Flag : INT_TYPE_FLAG
2023-9-1--[ Debug ]--Destroy SqQueue OKreal 0m0.002s
user 0m0.000s
sys 0m0.002s 七、快速排序基本思想
快速排序是改进的交换排序。
1、任取一个元素为中心一般是第一个元素。
2、所有比它小的元素一律前放比它大的元素一律后放形成左右两个子表。
3、对各子表重新选择中心元素并依照上述规则调整。
4、直到每个子表的元素只剩下一个。 八、快速排序算法实现思路 这里的哨兵位也是起到存放临时变量的作用的。
1、第一趟
1号位的3作为中间点存放在哨兵位0中那Low位置的元素就是空的了。 哨兵位的3和High的1进行比较3大于1将High的1填写到Low上那样High的位置就空出来了。我们开始从Low找。 哨兵位的3和Low的1进行比较3大于1在3的左边不需要移动Low向右移动。
哨兵位的3和Low的2进行比较3大于2在3的左边不需要移动Low向右移动。 哨兵位的3和Low的8进行比较8大于3在3的右边需要移动把Low的8移动到High的位置Low的位置空了开始High位置和哨兵进行比较是不是发现了什么左边有空位了就去右边找找右边空了就去左边找很有规律性。 哨兵位的3和High的8进行比较8大于3在3的右边不需要移动High向左移动。 哨兵位的3和High的6进行比较6大于3在3的右边不需要移动High向左移动。 哨兵位的3和High的4进行比较4大于3在3的右边不需要移动High向左移动。 Low和High重合说明Low左边的都比3小右边的都比3大把3填到Low的位置。
Low左边已经排好序了我们开始排序右边的这些元素。 2、第二趟
还是以第一个Low的位置为中心点这样Low的位置就空出来了哨兵和HIgh为的5进行比较发现比8小HIgh左移。 哨兵位的5和High的6进行比较6大于5在5的右边不需要移动High向左移动。 哨兵位的5和High的4进行比较5大于4在5的左边Low填上4那High的位置就空出来了我们开始移动Low。 哨兵位的5和Low的4进行比较5大于4在3的左边不需要移动Low向右移动。
发现Low和High重合将哨兵填写到Low上这一段有序了整个序列就完成了排序。 九、快速排序算法源码
1、QuickSortPartionSentrySqQueue
将Low到High之间元素根据Low为中间值进行分区返回中间值的最终索引位置。
//返回中间点索引。
QueueLenType QuickSortPartionSentrySqQueue(SqQueue* Queue, QueueLenType Low, QueueLenType High)
{JudgeAllNullPointer(Queue);int* Array (int*)(Queue-Data);Array[0] Array[Low];while (Low High){while (Low High Array[0] Array[High])//大于等于中间点的值放右边。{High--;}Array[Low] Array[High];while (Low High Array[0] Array[Low])//小于中间点的值放左边。{Low;}Array[High] Array[Low];}Array[Low] Array[0];return Low;
}
2、QuickSortRecurtionSentrySqQueue
void QuickSortRecurtionSentrySqQueue(SqQueue* Queue, QueueLenType Low, QueueLenType High)
{JudgeAllNullPointer(Queue);if (Low High)//退出条件High必须要大于low。{return;}QueueLenType PivotIndex QuickSortPartionSentrySqQueue(Queue, Low, High);QuickSortRecurtionSentrySqQueue(Queue, Low, PivotIndex - 1);QuickSortRecurtionSentrySqQueue(Queue, PivotIndex 1, High);
} 十、快速排序算法效率
情况时间复杂度是否稳定最好O(n * log2^n)不稳定最坏O(n^2)平均O(n * log2^n)
1、快速排序不是原地排序因为递归方法使用了系统栈不用递归需要用用户栈实现。
2、快速排序不适用于对原本有序或基本有序的记录序列进行排序。
3、划分元素的选取是影响时间性能的关键。
4、输入数据次序越乱所选划分值随机性越好排序速度越快快速排序不是自然排序方法。
5、升序快速排序算法使用在倒序排序序列上会触发最坏的情况使算法退化为冒泡排序。 十一、快速排序Linux环境编译测试
[gbaseczg2 Sort]$ time ./TestSort
2023-9-1--[ Debug ]--Init SqQueue OK
2023-9-1--[ Debug ]--Enter SqQueue OK
2023-9-1--[ Debug ]--Enter SqQueue OK
2023-9-1--[ Debug ]--Enter SqQueue OK
2023-9-1--[ Debug ]--Enter SqQueue OK
2023-9-1--[ Debug ]--Enter SqQueue OK
2023-9-1--[ Debug ]--Enter SqQueue OK
2023-9-1--[ Debug ]--Enter SqQueue OK
2023-9-1--[ Debug ]--Enter SqQueue OK
2023-9-1--[ Debug ]--Enter SqQueue OK
2023-9-1--[ Debug ]--Enter SqQueue OK
2023-9-1--[ Debug ]--Enter SqQueue OK
2023-9-1--[ Debug ]--SqQueue Data :
Data : [ 0 ,10 ,9 ,8 ,7 ,6 ,5 ,4 ,3 ,2 ,1 ]
FrontIndex : 0
RearIndex : 0
SqQueueLen : 11
SqQueueMaxLen : 11
Flag : INT_TYPE_FLAG
2023-9-1--[ Debug ]--Quick Sort Sentry SqQueue OK.
2023-9-1--[ Info ]--Sort Function Elapsed Time : 0 s
2023-9-1--[ Info ]--SqQueue Data :
Data : [ 4 ,0 ,1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ]
FrontIndex : 0
RearIndex : 0
SqQueueLen : 11
SqQueueMaxLen : 11
Flag : INT_TYPE_FLAG
2023-9-1--[ Debug ]--Destroy SqQueue OKreal 0m0.002s
user 0m0.000s
sys 0m0.002s
