Quick sort - 版本历史

Riguz：Riguz移动页面快速排序至Quick sort，不留重定向

2024-01-18T09:18:49Z

Riguz移动页面快速排序至Quick sort，不留重定向

←上一版本		2024年1月18日 (四) 09:18的版本
（没有差异）

imported>Soleverlee：/* Java */

2016-05-11T08:40:13Z

Java

←上一版本		2016年5月11日 (三) 08:40的版本
第221行：		第221行：

	==Java==		==Java==
			<source lang="java">
			class QuickSort{
			public static void main(String[] args) {
			int arr[] = {9,4,8,3,1,2,5};
			System.out.println("Initial Array");
			System.out.println(Arrays.toString(arr));
			quickSort(arr, 0, arr.length-1);
			System.out.println(Arrays.toString(arr));
			}
			private static void quickSort(int[] arr, int low, int high) {
			if(low < high){
			int pos = partition(arr, low, high);
			quickSort(arr, low, pos-1);
			quickSort(arr, pos+1, high);
			}
			}

			private static int partition(int[] arr, int low, int high) {
			int pivot = arr[high]; //以最右边的元素为轴
			int small = low - 1; //记录比轴小的左侧元素区间[low - small]
			for(int k = low; k < high; k++){ //遍历low -> hight区间
			if(arr[k] <= pivot){ //如果发现元素小于等于轴，则将元素移动到左侧
			small++; //同时更新左侧元素区间
			swap(arr, k, small);
			}
			}
			int nextPivot = small + 1;
			swap(arr, high, nextPivot); //将轴移动到左侧区间[low- small] pivot ->high
			return nextPivot; //返回轴的新位置
			}

			private static void swap(int[] arr, int k, int small) {
			int temp;
			temp = arr[k];
			arr[k] = arr[small];
			arr[small] = temp;
			}
			}
			</source>
	[[Category:Algorithm]]		[[Category:Algorithm]]

imported>Soleverlee：/* Python */

2016-05-11T08:31:43Z

Python

←上一版本		2016年5月11日 (三) 08:31的版本
第219行：		第219行：
	qsort([x for x in arr[1:] if x >= pivot])		qsort([x for x in arr[1:] if x >= pivot])
	</source>		</source>

			==Java==

	[[Category:Algorithm]]		[[Category:Algorithm]]

imported>Soleverlee：/* C */

2015-03-27T09:50:52Z

@@ 第169行： / 第169行： @@
 </source>
-==C==
+==C#==
-<source lang="c">
+<source lang="csharp">
 </source>
 [[Category:Algorithm]]

imported>Soleverlee：/* C */

2015-03-27T09:48:54Z

←上一版本		2015年3月27日 (五) 09:48的版本
第141行：		第141行：
	</source>		</source>
	未使用STL的快速排序版本:		未使用STL的快速排序版本:
	<source lang="c>		<source lang="c">
	#include <utility>		#include <utility>
	using std::swap;		using std::swap;

imported>Soleverlee：/* C */

2015-03-27T09:48:38Z

@@ 第101行： / 第101行： @@
+}
 </source>
 #include <functional>
 #include <algorithm>
@@ 第137行： / 第139行： @@
    );
+}
 <source lang="c>
 </source>

imported>Soleverlee：/* C */

2015-03-27T09:47:16Z

←上一版本		2015年3月27日 (五) 09:47的版本
第84行：		第84行：
	</source>		</source>
	C89标准在stdlib.h中定义了抽象数据类型的快速排序函数qsort(3)。		C89标准在stdlib.h中定义了抽象数据类型的快速排序函数qsort(3)。
	<source lang="c>		<source lang="c">
	#include <stdio.h>		#include <stdio.h>
	#include <stdlib.h>		#include <stdlib.h>

imported>Soleverlee：/* C */

2015-03-27T09:46:52Z

@@ 第45行： / 第45行： @@
 ==C==
 <source lang="c">
 </source>
 ==C==
 <source lang="c">

imported>Soleverlee：/* C */

2015-03-27T09:03:09Z

@@ 第11行： / 第11行： @@
 递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
 =示例代码=
-==C==
+==C++(迭代版本）==
-<source lang="c">
+<source lang="cpp">
 </source>
 ==C==
 <source lang="c">

imported>Soleverlee：以“使用快速排序法对一列数字进行排序的过程快速排序是由东尼·霍尔所发展的一种排序...”为内容创建页面

2015-03-27T09:01:36Z

以“right|frame|使用快速排序法对一列数字进行排序的过程快速排序是由东尼·霍尔所发展的一种排序...”为内容创建页面

新页面

[[Image:Sorting_quicksort_anim.gif|right|frame|使用快速排序法对一列数字进行排序的过程]]
快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序n个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(n log n)算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。
=算法描述=
快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。

步骤为：

#从数列中挑出一个元素，称为"基准"（pivot），
#重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个#分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
#递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
=示例代码=
==C==
<source lang="c">
</source>
==C==
<source lang="c">
</source>
==C==
<source lang="c">
</source>

[[Category:Algorithm]]

Quick sort - 版本历史

Riguz：​Riguz移动页面快速排序至Quick sort，不留重定向

imported>Soleverlee：​/* Java */

imported>Soleverlee：​/* Python */

imported>Soleverlee：​/* C */

imported>Soleverlee：​/* C */

imported>Soleverlee：​/* C */

imported>Soleverlee：​/* C */

imported>Soleverlee：​/* C */

imported>Soleverlee：​/* C */

imported>Soleverlee：​以“使用快速排序法对一列数字进行排序的过程 快速排序是由东尼·霍尔所发展的一种排序...”为内容创建页面

Riguz：Riguz移动页面快速排序至Quick sort，不留重定向

imported>Soleverlee：/* Java */

imported>Soleverlee：/* Python */

imported>Soleverlee：/* C */

imported>Soleverlee：/* C */

imported>Soleverlee：/* C */

imported>Soleverlee：/* C */

imported>Soleverlee：/* C */

imported>Soleverlee：/* C */

imported>Soleverlee：以“使用快速排序法对一列数字进行排序的过程快速排序是由东尼·霍尔所发展的一种排序...”为内容创建页面