C#，双向链表（Doubly Linked List）快速排序（Quick Sort）算法与源代码

双向链表

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

循环链表是一种链式存储结构，它的最后一个结点指向头结点，形成一个环。因此，从循环链表中的任何一个结点出发都能找到任何其他结点。循环链表的操作和单链表的操作基本一致，差别仅仅在于算法中的循环条件有所不同。

快速排序（Quick Sort）

快速排序是非常流行、应用非常广泛的排序算法，而且实现简单，适用于各种不同的输入数据，在一般应用中比其他排序算法都要快很多。快速排序是基于分治思想的原地排序的排序算法，将长度为N的数组排序所需时间和NlgN成正比，而且内循环比大多数排序算法都要短小和简单，因此一般情况比其他排序算法效率高。它的缺点是非常脆弱，某些情况可能导致它的性能达到平方级别，因此实现时必须非常小心才能避免低劣的性能。
快速排序的整体思路是根据某个元素将一个数组分成左右两个子数组，以该元素为界限，左侧子数组的值都小于或等于该元素，右侧子数组的值都大于或等于该元素（这一过程称为切分，下面会介绍）。然后递归地对数组的左右两个子数组继续进行上述操作，直到所有元素排列完成。上述每一趟切分都能排定一个元素（切分元素），如果左子数组和右子数组都是有序的，那么由左子数组、切分元素、右子数组组成的数组一定是有序的。

切分的详细过程
一般选取数组第一个元素为切分元素，也是那个会被排定的元素，然后定义两个指针，一个指针从数组左侧第二个元素开始向右侧遍历数组，直到找到一个大于或等于切分元素的元素时停止；另一个指针从数组右侧最后一个元素开始向左侧遍历数组，直到找到一个小于或等于切分元素的元素时停止，然后交换两个元素的位置。如此继续，直到两个指针相遇，然后将切分元素和左子数组最右侧元素交换位置，并返回交换后的切分元素位置即可。这样每一趟切分都能排定切分元素，并保证切分元素左侧的元素都小于或等于它，右侧的元素都大于或等于它。

源程序

public class DoublyLinkNode
{
	public int Data { get; set; } = 0;
	public DoublyLinkNode Next { get; set; } = null;
	public DoublyLinkNode Prev { get; set; } = null;
	public DoublyLinkNode(int d)
	{
		Data = d;
	}
}

using System;
using System.Text;
using System.Collections;
using System.Collections.Generic;

namespace Legalsoft.Truffer.Algorithm
{
	public partial class DoublyLinkedList
	{
		private DoublyLinkNode LastNode(DoublyLinkNode node)
		{
			while (node.Next != null)
			{
				node = node.Next;
			}
			return node;
		}

		private DoublyLinkNode Partition(DoublyLinkNode last, DoublyLinkNode head)
		{
			int pivot = head.Data;

			DoublyLinkNode i = last.Prev;
			for (DoublyLinkNode j = last; j != head; j = j.Next)
			{
				if (j.Data <= pivot)
				{
					// Similar to i++ for array
					i = (i == null) ? last : i.Next;
					{
						int temp = i.Data;
						i.Data = j.Data;
						j.Data = temp;
					}
				}
			}
			i = (i == null) ? last : i.Next;
			{
				int temp = i.Data;
				i.Data = head.Data;
				head.Data = temp;
			}
			return i;
		}

		private void QuickSort_Utility(DoublyLinkNode last, DoublyLinkNode head)
		{
			if (head != null && last != head && last != head.Next)
			{
				DoublyLinkNode temp = Partition(last, head);
				QuickSort_Utility(last, temp.Prev);
				QuickSort_Utility(temp.Next, head);
			}
		}

		public void QuickSort(DoublyLinkNode node)
		{
			DoublyLinkNode head = LastNode(node);
			QuickSort_Utility(node, head);
		}

		public DoublyLinkNode Push(DoublyLinkNode head, int d)
		{
			DoublyLinkNode node = new DoublyLinkNode(d);
			node.Next = head;
			head.Prev = node;
			return node;
		}
	}
}