Created
August 18, 2014 13:15
-
-
Save xd547/bcb4c8314f8feacd5711 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| using System; | |
| using System.Collections.Generic; | |
| using System.Text; | |
| using System.IO; | |
| using System.Diagnostics; | |
| namespace sort | |
| { | |
| class Program | |
| { | |
| static void Main(string[] args) | |
| { | |
| //读取文件 | |
| string filename = "D:\\test1000000.txt"; | |
| FileInfo fi = new FileInfo(filename); | |
| List<int> array = new List<int>(); | |
| if (!fi.Exists) | |
| { | |
| Console.WriteLine("文件{0}不存在！", filename); | |
| Console.Read(); | |
| return; | |
| } | |
| using (StreamReader sr = fi.OpenText()) | |
| { | |
| while (sr.Peek() >= 0) | |
| { | |
| string line = sr.ReadLine(); | |
| int result; | |
| //对读入内容进行检测 | |
| if (int.TryParse(line, out result)) | |
| { | |
| array.Add(int.Parse(line)); | |
| } | |
| } | |
| } | |
| Stopwatch stopwatch = new Stopwatch(); | |
| stopwatch.Start(); | |
| //array.Sort();//这个是内置的排序，可以使用自定义的ICompare接口 | |
| //冒泡排序 | |
| /* | |
| for (int i = 0; i < array.Count; i++) | |
| { | |
| for (int j = i + 1; j < array.Count; j++) | |
| { | |
| int temp; | |
| if (array[i] > array[j]) | |
| { | |
| temp = array[i]; | |
| array[i] = array[j]; | |
| array[j] = temp; | |
| } | |
| } | |
| } | |
| */ | |
| //合并排序 | |
| //Program.MergeSort(ref array, 1, array.Count); | |
| Program.Bitmap(ref array); | |
| stopwatch.Stop(); | |
| for (int i = 0; i < 20; i++) | |
| { | |
| Console.WriteLine(array[i]); | |
| } | |
| Console.WriteLine("split line"); | |
| for (int i = array.Count - 20; i < array.Count; i++) | |
| { | |
| Console.WriteLine(array[i]); | |
| } | |
| Console.WriteLine("sort time: {0} ms", stopwatch.ElapsedMilliseconds); | |
| Console.Read(); | |
| } | |
| private static void Merge(ref List<int> array, int p, int q, int r) | |
| { | |
| int n_l = q - p + 1; //计算左部长度 | |
| int n_r = r - q; //计算右部长度 | |
| int[] L = new int[n_l + 1]; | |
| int[] R = new int[n_r + 1]; | |
| //拷贝左部 | |
| for (int i = 1; i <= n_l; i++) | |
| { | |
| L[i - 1] = array[p + i - 1 -1]; | |
| } | |
| //拷贝右部 | |
| for (int i = 1; i <= n_r; i++) | |
| { | |
| R[i - 1] = array[q + i - 1]; | |
| } | |
| //设置令牌 | |
| L[n_l] = int.MaxValue; | |
| R[n_r] = int.MaxValue; | |
| int m = 1; | |
| int n = 1; | |
| //合并左部及右部 | |
| for (int k = p; k <= r; k++) | |
| { | |
| if (L[m - 1] <= R[n -1]) | |
| { | |
| array[k - 1] = L[m - 1]; | |
| m++; | |
| } | |
| else | |
| { | |
| array[k - 1] = R[n - 1]; | |
| n++; | |
| } | |
| } | |
| } | |
| private static void MergeSort(ref List<int> array, int p, int r) | |
| { | |
| //p < r说明子数组的长度不为1 | |
| if (p < r) | |
| { | |
| //将数组分为两半，递归调用。 | |
| int q = ((p + r) / 2); | |
| Program.MergeSort(ref array, p, q); | |
| Program.MergeSort(ref array, q + 1, r); | |
| Program.Merge(ref array, p, q, r); | |
| } | |
| } | |
| private static void Bitmap(ref List<int> arrary) | |
| { | |
| int n = arrary.Count; | |
| bool[] bit = new bool[n + 1]; | |
| /* | |
| for (int i = 0; i < n; i++) | |
| { | |
| bit[i] = false; | |
| } | |
| */ | |
| foreach (int i in arrary) | |
| { | |
| bit[i] = true; | |
| } | |
| for (int i = 0; i < n; i++) | |
| { | |
| if (bit[i]) | |
| { | |
| arrary[i] = i + 1; | |
| } | |
| } | |
| } | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment