- using System;
- using System.Collections.Generic;
- using System.Collections.ObjectModel;
- using System.Diagnostics;
- using System.IO;
- using System.Text;
- namespace SortAlgorithom
- {
- public class SortAlgorithm<T> where T : IComparable<T>
- {
- Stopwatch stopwatch = new Stopwatch();
- public void Sort(IList<T> collection)
- {
- if (collection != null)
- {
- stopwatch.Restart();
- DoSort(collection);
- stopwatch.Stop();
- Console.WriteLine("{0}: {1}", this.ToString(), stopwatch.Elapsed);
- }
- }
- protected virtual void DoSort(IList<T> collection)
- {
- // Nothing to do.
- }
- }
- public class InsertSort<T> : SortAlgorithm<T> where T : IComparable<T>
- {
- protected override void DoSort(IList<T> collection)
- {
- T key;
- for (int j = 1, i = 0; j < collection.Count; j++)
- {
- key = collection[j];
- i = j - 1;
- while (i > -1 && collection[i].CompareTo(key) > 0)
- {
- collection[i + 1] = collection[i];
- i--;
- }
- collection[i + 1] = key;
- }
- }
- public override string ToString()
- {
- return "InsertSort";
- }
- }
- public class MergeSort<T> : SortAlgorithm<T> where T : IComparable<T>
- {
- protected override void DoSort(IList<T> collection)
- {
- DoMergeSort(collection, 0, collection.Count - 1);
- }
- private void Merge(IList<T> collection, int p, int q, int r)
- {
- IList<T> leftCollection = new Collection<T>();
- IList<T> rightCollection = new Collection<T>();
- int n1 = q - p + 1;
- int n2 = r - q;
- int i, j, k;
- for (i = 0; i < n1; i++)
- {
- leftCollection.Add(collection[i + p]);
- }
- for (i = 0; i < n2; i++)
- {
- rightCollection.Add(collection[i + q + 1]);
- }
- for (k = p, i = 0, j = 0; i < n1 && j < n2; k++)
- {
- if (leftCollection[i].CompareTo(rightCollection[j]) < 0)
- {
- collection[k] = leftCollection[i ++];
- }
- else
- {
- collection[k] = rightCollection[j ++];
- }
- }
- if (i < n1)
- {
- for (; i < n1; i++, k++)
- {
- collection[k] = leftCollection[i];
- }
- }
- else if (j < n2)
- {
- for (; j < n2; j++, k++)
- {
- collection[k] = rightCollection[j];
- }
- }
- else
- {
- // Nothing to do.
- }
- }
- private void DoMergeSort(IList<T> collection, int p, int r)
- {
- if (p < r)
- {
- int q = (p + r) / 2;
- DoMergeSort(collection, p, q);
- DoMergeSort(collection, q + 1, r);
- Merge(collection, p, q, r);
- }
- }
- public override string ToString()
- {
- return "MergeSort";
- }
- }
- public class HeapSort<T> : SortAlgorithm<T> where T : IComparable<T>
- {
- protected override void DoSort(IList<T> collection)
- {
- DoHeapSort(collection);
- }
- private void HeapAdjust(IList<T> collection, int s, int m)
- {
- T key = collection[s];
- for (int i = s * 2 + 1; i <= m; i = i * 2 + 1)
- {
- if (i < m && collection[i].CompareTo(collection[i + 1]) < 0)
- {
- i++;
- }
- if (collection[i].CompareTo(key) < 0)
- {
- break;
- }
- collection[s] = collection[i];
- s = i;
- }
- collection[s] = key;
- }
- private void DoHeapSort(IList<T> collection)
- {
- int maxIndex = collection.Count - 1;
- int i;
- for (i = maxIndex / 2; i >= 0; i--)
- {
- HeapAdjust(collection, i, maxIndex);
- }
- for (i = maxIndex; i > 0; i--)
- {
- T key = collection[0];
- collection[0] = collection[i];
- collection[i] = key;
- HeapAdjust(collection, 0, i - 1);
- }
- }
- public override string ToString()
- {
- return "HeapSort";
- }
- }
- public class Program
- {
- const int DefaultSortNum = 10000;
- static void Main(string[] args)
- {
- int sortNum;
- while (true)
- {
- int.TryParse(Console.ReadLine(), out sortNum);
- if (sortNum <= 0)
- {
- sortNum = DefaultSortNum;
- }
- List<int> source = Utility.GenerateNums(sortNum);
- List<int> source1 = new List<int>(source);
- List<int> source2 = new List<int>(source);
- List<int> source3 = new List<int>(source);
- List<int> source4 = new List<int>(source);
- InsertSort<int> insertSort = new InsertSort<int>();
- MergeSort<int> mergeSort = new MergeSort<int>();
- HeapSort<int> heapSort = new HeapSort<int>();
- insertSort.Sort(source1);
- mergeSort.Sort(source2);
- heapSort.Sort(source3);
- Utility.WriteToFile(insertSort.ToString(), source1);
- Utility.WriteToFile(mergeSort.ToString(), source2);
- Utility.WriteToFile(heapSort.ToString(), source3);
- }
- }
- }
- public static class Utility
- {
- public static List<int> GenerateNums(int count)
- {
- if (count < 0)
- {
- return null;
- }
- List<int> result = new List<int>();
- Random random = new Random();
- int i = 0;
- while (i++ < count)
- {
- result.Add(random.Next());
- }
- return result;
- }
- public static void WriteToFile(string fileName, List<int> collection)
- {
- using (FileStream fs = new FileStream(fileName, FileMode.OpenOrCreate, FileAccess.Write))
- {
- using (StreamWriter sw = new StreamWriter(fs, Encoding.UTF8))
- {
- foreach (int i in collection)
- {
- sw.WriteLine(i.ToString());
- }
- }
- }
- }
- }
- }
- //该片段来自于http://www.codesnippet.cn/detail/1808201614937.html
来源: http://www.codesnippet.cn/detail/1808201614937.html