竞价网站怎么做seo,河北中保建设集团网站首页,企业网站优化官网,软件园专业做网站快速排序#xff08;Quick Sort#xff09;是一种常见的排序算法#xff0c;由英国计算机科学家东尼霍尔#xff08;Tony Hoare#xff09;在1960年发明。这是一种分治算法#xff0c;基本思想是通过一趟排序将要排序的数据分割成独立的两部分#xff0c;其中一部分的所…快速排序Quick Sort是一种常见的排序算法由英国计算机科学家东尼·霍尔Tony Hoare在1960年发明。这是一种分治算法基本思想是通过一趟排序将要排序的数据分割成独立的两部分其中一部分的所有数据都比另外一部分的所有数据要小然后再按此方法对这两部分数据分别进行快速排序整个排序过程可以递归进行以此达到整个数据变成有序序列。
快速排序算法在平均状况下排序 n 个项目要 Ο(n log n) 次比较。在最坏状况下则需要 Ο(n^2) 次比较但这种状况并不常见。实际上快速排序通常明显比其他 Ο(n log n) 算法更快因为它的内部循环inner loop可以在大部分的架构上很有效率地达成。
快速排序的一个优点是它是不稳定的排序算法意味着相同的元素在排序后可能会保持其原有的顺序。
下面是一个伪代码示例 快速排序(数组 a, 长度 n) 如果 n 1 选择 a[1] 作为基准值 左 1 右 n 当 左 右 当 a[右] 基准值 右 右 - 1 当 a[左] 基准值 左 左 1 交换 a[左] 和 a[右] 快速排序(a, 左 右) 在这个算法中我们选择数组的中位数作为基准值然后将数组分为两部分一部分是所有小于基准值的元素另一部分是所有大于或等于基准值的元素。然后对这两部分递归地进行快速排序。
在实际应用中快速排序是效率非常高的一种排序算法尤其是在处理大量数据时。
ok,下面是代码
#includestdio.h
int a[100], n;
void qs(int left, int right)
{int i, j, t, temp;if (left right)return;temp a[left];i left;j right;while (i ! j){while (a[j] temp i j){j--;}while (a[i] temp i j){i;}if (i j){t a[i];a[i] a[j];a[j] t;}} a[left] a[i];a[i] temp;qs(left, i - 1);qs(i 1, right);
}int main()//快速排序
{int i, j, t;scanf(%d, n);for (int i 1; i n; i){scanf(%d, a[i]);}qs(1, n);for (int i 1; i n; i){printf(%d , a[i]);}return 0;
}
