算法思想:
在实际应用当中快速排序确实也是表现最好的排序算法. 其思想是来自冒泡排序, 冒泡排序是通过相邻元素的比较和交换把最小的冒泡到最顶端, 而快速排序是比较和交换小数和大数, 这样一来不仅把小数冒泡到上面同时也把大数沉到下面.
它采用了一种分治的策略, 分治法的基本思想是: 将原问题分解为若干个规模更小但结构与原问题相似的子问题. 递归地解这些子问题, 然后将这些子问题的解组合为原问题的解.
快速排序是不稳定的, 其时间平均时间复杂度是 O(nlgn).
举例:
5,3,8,6,4 用 5 作为比较的基准, 最终会把 5 小的移动到 5 的左边, 比 5 大的移动到 5 的右边.
5,3,8,6,4 首先设置 i,j 两个指针分别指向两端, 将左端元素 5 赋值给 temp,j 指针先扫描, 4 比 5 小停止, 执行 a[i]=a[j]
4,3,8,6,4 然后 j 指针再扫描, 遇到 8 比 temp 大, 此时 i 停在 8,j 停在 4, 执行 a[j]=a[i]
4,3,8,6,8 此时 j 往前走直到和 i 相遇, 此时的 i 就是 temp 应该放的位置
4,3,5,6,8 之后对左右子序列递归排序, 最终得到有序序列.
代码:
- void quickSort(int* a, int left, int right)
- {
- int i = left;
- int j = right;
- int temp = a[left];
- if (left>= right)
- return;
- while (i != j)
- {
- while (i <j&&a[j]>= temp)
- j--;
- if (j> i)
- a[i] = a[j];
- while (i < j&&a[i] <= temp)
- i++;
- if (i < j)
- a[j] = a[i];
- }
- a[i] = temp;// 把基准插入
- quickSort(a, left, i - 1);/* 递归左边 */
- quickSort(a, i + 1, right);/* 递归右边 */
- }
来源: http://www.bubuko.com/infodetail-3499222.html