数据结构与算法之三 深入学习排序

快速排序算法 ：

快速排序是最有效率的排序算法之一，此算法基于 分治法

连续 将问题 细分为更小的问题 ， 直到 问题 成为可以直接解决的小问题

在快速排序算法中，你：

从名为 枢轴 的列表处选择元素 。

将列表划分为两部分 ：

列表左端的所有元素 小于等于 枢轴 。

列表右端的所有元素 大于 枢轴 。

在此列表两部分的 正确位置 存储 枢轴 。

划分之后为创建的 两个子列表重复 此过程 ( 找枢轴的过程 ) 。

直到 每个子列表中只剩一个元素 。

思想：就是不断找出符合条件的枢轴位置

编写一个算法以实现快速排序：

QuickSort(low,high)

1. 如果 (low > high):

  a.  返回

2. 设置 pivot = arr[low]

3. 设置 i = low + 1

4. 设置 j = high

5. 重复第 6 步直到 i > high 或 arr[i] > pivot // 搜索大于枢轴的元素

6. 按 1 递增 i

7. 重复第 8 步直到 j < low 或 arr[j] < pivot // 搜索小于枢轴的元素

      8. 按 1 递减 j

9. 如果 i < j: // 如果较大的元素位于较小元素的左侧

  a.  交换 arr[i] 与 arr[j]

10. 如果 i <= j:

  a.  转到第 5 步 // 继续搜索

11. 如果 low < j:

  a.  交换 arr[low] 与 arr[j] // 交换枢轴与列表第一部分的最后一个元素

12. QuickSort(low,J – 1) // 对枢轴左侧的列表应用快速排序

13. QuickSort(J + 1, high) // 对枢轴右侧的列表应用快速排序

此排序算法的总时间取决于枢轴值的位置。

最糟的情形出现在列表已经排序时。

通常，选择第一个元素作为枢轴，但是其会导致 O(n2) 的最糟用例效率。

如果您选择所有值的中间值作为枢轴 ，则效率将是 O(n log n) 。

什么是快速排序算法的平均用例的比较总次数。

答案：

O(n log n)

归并排序算法：

其使用分治法来排序列表

要排序的列表将分为两个几乎相等的两个子列表

这两个子列表将通过使用归并排序单独排序

这两个排序的子列表归并为单个排序的列表

编写一个算法以实现归并排序：

MergeSort(low,high)

1. 如果 (low >= high):

  a.  返回 调用本函数的地方 .

2. 设置 mid = (low + high)/2

3. 将列表划分为几乎完全相等的两个子列表，并通过使用归并排序来排序每个子列表。 执行的步骤如下： :

    a. MergeSort （ low, mid ）

  b. MergeSort （ mid + 1, high ）

4. 归并两个排序的子列表：通过一 merge() 方法实现 .

  a. 设置 i = low 

    b. 设置 j = mid + 1

  c. 设置 k = low

  d. 重复直到 i > mid 或 j > high: //  此循环将终止，前提是达到两个子列表的其中一个结束处。  

 

  i. 如果 (arr[I] <= arr[J])

     将 arr[I] 存储到数组 B 中的索引 k 处

        按 1 递增 i

   Else

将 arr[j] 存储到数组 B 中的索引 k 处

按 1 递增 j

     ii. 按 1 递增 k

  e. 重复直到 j > high: // 如果第二个中仍然有某些元素                                                                       // 追加到新列表的子列表

  i. 将 arr[j] 存储到数组 B 中的索引 k 处

  ii. 按 1 递增 j

  iii. 按 1 递增 k

  f. 重复直到 i > mid:  // 如果在第一个子列表中仍然有一些元素

                                            // 将它们追加到新类别中

  i. 将 arr[i] 存储到数组 B 中的索引 k 处

  ii. 按 1 递增 i

  iii. 按 1 递增 k

5. 将排序的数组 B 中的所有元素复制到原始数组 arr 中

若要排序此列表，您需要按递归方式将列表划分为两个几乎完全相等的子列表，直 到每个子列表仅包含一个元素。

  将列表划分为大小为 1 的子列表需要 log n 次通行。

在每个通行中 ，最多执行 n 次比较。

  因此，比较总数将是最多 n × log n 次。

归并排序的效率等于 O(n log n) 。

归并列表的最佳、平均和最糟用例效率之间没有差异 ，因为所有这些效率均需要相 同的时间量。

哪个算法使用以下步骤来排序给出的元素列表？

       1.      选择名为枢轴的列表中的元素。

      2. 将列表分为两个部分，以便一部分包含小于枢轴的元素，另一部分包含大于枢 轴的元素。

      3. 然后将枢轴放到两个列表之间的正确位置。

      4. 使用相同的算法排序列表的两个部分。

答案：

快速排序

/*
问题描述：编写在数组中存储10个数字的程序，并通过使用快速排序算法来排序。
*/
using System;
using System.Text;

class Merge_Sort
{
	private int[]arr=new int[20];	//定义数组，你输入数字，接受存储的数组
	private int[]dest=new int[20];	//在归并排序中用来存储已经排序的数组，就是咱说的新数组.
	private int cmp_count;	//比较总次数
	private int mov_count;	//移动总次数
	//数组元素个数
	public int n;
	//****************构造方法
	public Merge_Sort()
	{
		cmp_count=0;
		mov_count=0;	
	}	
	//用户输入数据方法
	void read()
	{
		while(true)
		{
			Console.WriteLine("请输入数组的元素个数:");
			string s=Console.ReadLine();
			n=Int32.Parse(s);
			if(n<=20)
				break;
			else
				Console.WriteLine("\n数组的最大元素个数为20.\n");	
		}
		Console.WriteLine("\n---------------------------------");
		Console.WriteLine("-----------请输入数组元素---------");
		Console.WriteLine("---------------------------------");
		//获得数组元素
		for(int i=0;i