须知的C#常用的排序方法.doc

排序大全1.稳定性比较插入排序、冒泡排序、二叉树排序、归并排序及其他线形排序是稳定的选择排序、希尔排序、快速排序、堆排序是不稳定的2.时间复杂性比较插入排序、冒泡排序、选择排序的时间复杂性为O(n2)其它非线形排序的时间复杂性为O(nlog2n)线形排序的时间复杂性为O(n);3.辅助空间的比较归并排序的辅助空间为O(n),其它排序的辅助空间为O(1);4. C# Codes4.1 冒泡排序class Programstatic void Main(string args)int array = new int 6, 6, 5, 4, 3, 2, 1, 0 ;array = Sort(array);foreach (var item in array)Console.WriteLine(item.ToString();Console.ReadKey();static int Sort(int array)for (int i = 0; i array.Length; i+)for (int j = 0; j array.Length - i -1; j+)if (arrayj+1 arrayj)Swap(array, j, j+1);return array;static void Swap(int array, int firstIndex, int secondIndex)int preserve = arrayfirstIndex;arrayfirstIndex = arraysecondIndex;arraysecondIndex = preserve;4.2 简单选择排序class Programstatic void Main(string args)int array = new int 6, 6, 5, 4, 3, 2, 1, 0 ;array = SelectSort(array);foreach (var item in array)Console.WriteLine(item.ToString();Console.ReadKey();static int SelectSort(int array)for (int i = 0; i array.Length; i+)for (int j = i; j array.Length; j+)if (arrayj arrayi)Swap(array, j, i);return array;static void Swap(int array, int firstIndex, int secondIndex)int preserve = arrayfirstIndex;arrayfirstIndex = arraysecondIndex;arraysecondIndex = preserve;4.3 快速排序class Programstatic void Main(string args)int array = new int 6, 6, 5, 4, 3, 2, 1, 0 ;array = QuickSort(array, 0, array.Length - 1);foreach (var item in array)Console.WriteLine(item.ToString();Console.ReadKey();static int QuickSort(int array,int start, int end)int low = start;int high = end;int mark = start;while (low high)while (low arraymark)Swap(array, low, mark);mark = low;continue;elselow+;while (mark arrayhigh)Swap(array, high, mark);mark = high;continue;elsehigh-;if (mark - start 1)QuickSort(array, start, mark-1);if (end - mark 1)QuickSort(array, mark+1, end);return array;static void Swap(int array, int firstIndex, int secondIndex)int preserve = arrayfirstIndex;arrayfirstIndex = arraysecondIndex;arraysecondIndex = preserve;4.4 堆排序class Programstatic void Main(string args)int array = new int 5,6,7,8,2,3,4,6,5,4,3,2 ;array = HeapSort(array);foreach (var item in array)Console.WriteLine(item.ToString();Console.ReadKey();public static void CreateHeap(int array, int lastIndex)for (int i = lastIndex; i 0; i-)if (arrayi arrayi / 2)Swap(array, i, i / 2);public static int HeapSort(int array)for (int i = array.Length - 1; i 0; i-)CreateHeap(array, i);Swap(array, 0, i);return array;static void Swap(int array, int firstIndex, int secondIndex)int preserve = arrayfirstIndex;arrayfirstIndex = arraysecondIndex;arraysecondIndex = preserve;4.5 二分插入排序class Programstatic void Main(string args)int array = new int 3,2,1,4,5,67,678678,234234,2,3,4,5,6,7,8,4 ;array = HalfInsertSort(array);foreach (var item in array)Console.WriteLine(item.ToString();Console.ReadKey();public static int HalfInsertSort(int array)for (int i = 0; i array.Length; i+)int start = 0;int end = i - 1;while (start = end)int middle = (start + end) / 2;if (arraymiddle start; j-)arrayj = arrayj - 1;arraystart = insertValue;return array;4.6 直接插入排序class Programstatic void Main(string args)int array = new int 6, 6, 5, 4, 3, 2, 1, 0 ;array = InsertSort(array);foreach (var item in array)Console.WriteLine(item.ToString();Console.ReadKey();static int InsertSort(int array)for (int i = 0; i array.Length; i+)for (int j = 0; j arrayi)Swap(array, j, i);return array;static void Swap(int array, int firstIndex, int secondIndex)int preserve = arrayfirstIndex;arrayfirstIndex = arraysecondIndex;arraysecondIndex = preserve;4.7 归并排序class Programstatic void Main(string args)int array = new int 1,1,2,2,2,2,3,3,2,2,2,22222222,1,1,1,1,1,1,1,1,0,0,0,0,7;array = MergeSort(array, 0, array.Length - 1);foreach (var item in array)Console.WriteLine(item.ToString();Console.ReadKey();public static int MergeSort(int array, int start, int end)int middle = start;if (start end)middle = (start + end) / 2;MergeSort(array, start, middle);MergeSort(array, middle + 1, end);Merge(array, start, end);return array;public static void Merge(int array, int start, int end)int middle = (start + end) / 2;Queue container = new Queue();int first = start;int second = middle + 1;while (first = middle & second = end)if (arrayfirst arraysecond)container.Enqueue(arrayfirst+);elsecontainer.Enqueue(arraysecond+);while (first = middle)container.Enqueue(arrayfirst+);while (second = end)container.Enqueue(arraysecond+);for (int i = start; i 0)for (int