代码展示:
1 using System;
2 using System.Collections.Generic;
3 using System.Linq;
4 using System.Text;
5 using System.Threading.Tasks;
6
7 namespace paixu
8 {
9 class Program
10 {
11 static void Main()
12 {
13 int[] Array = { 1, 45, 8, 65, 478, 5, 56, 1, 0, -87, 878, 4, 64 };
14
15 MaoPao(Array);
16 Console.WriteLine("-----------冒泡--------------------------");
17 KuaiSu01(Array);
18 Console.WriteLine("-----------快速法(一)-------------------");
19 KuaiSu02(Array);
20 Console.WriteLine("-----------快速法(二)-------------------");
21
22 string x = "=========以下两种查找方法必须要有序数组=============";
23
24 LaGeLangRi(Array, 878);
25 Console.WriteLine("-----------拉格朗日插值查找法-----------");
26 Dichotomy(Array,0);
27 Console.WriteLine("-----------二分法查找法-----------------");
28
29 Console.Read();
30 }
31 //---------------------冒泡------------------------------------------------
32 public static void MaoPao( int [] array)
33 {
34 int temp = 0;
35 for (int i = 0; i < array.Length-1; i )
36 {
37 for (int j = 0; j < array.Length - 1 - i; j )
38 {
39 if (array[j] > array[j 1])
40 {
41 temp = array[j];
42 array[j] = array[j 1];
43 array[j 1] = temp;
44 }
45 }
46 }
47 foreach (int item in array)
48 {
49 Console.WriteLine(item);
50 }
51 }
52 //---------------------快速(法一)------------------------------------------------------
53 public static void KuaiSu01( int [] array)
54 {
55 List <int> list = array.ToList();
56 QuickSort(list, 0, array.Length - 1);
57 foreach (int i in list)
58 {
59 Console.WriteLine(i.ToString());
60 }
61 }
62 private static int Division(List<int> list, int left, int right)//获取按枢轴值左右分流后枢轴的位置
63 {
64 while (left < right)
65 {
66 int num = list[left]; //将首元素作为枢轴
67 if (num > list[left 1])
68 {
69 list[left] = list[left 1];
70 list[left 1] = num;
71 left ;
72 }
73 else
74 {
75 int temp = list[right];
76 list[right] = list[left 1];
77 list[left 1] = temp;
78 right--;
79 }
80 }
81 return left; //指向的此时枢轴的位置
82 }
83 private static void QuickSort(List<int> list, int left, int right)//递归进行操作
84 {
85 if (left < right)
86 {
87 int i = Division(list, left, right);
88 //对枢轴的左边部分进行排序
89 QuickSort(list, i 1, right);
90 //对枢轴的右边部分进行排序
91 QuickSort(list, left, i - 1);
92 }
93 }
94 //---------------------快速(法二)-------------------------------------------------------
95 public static void KuaiSu02(int[] array)
96 {
97
98 Sort(array, 0, array.Length);
99 foreach (int i in array)
100 {
101 Console.WriteLine(i.ToString());
102 }
103 }
104 public static void Sort(int[] nums, int left, int right)//数组,起始下标,数组长度
105 {
106 if (left < right) //直到排序的左右区间只剩一个值
107 {
108 int i = left;
109 int j = right - 1;
110 int middle = nums[(left right) / 2];
111 while (true)
112 {
113 while (i < right && nums[i] < middle) { i ; };
114 //在middle左边找到一个比middle小的值
115 while (j > 0 && nums[j] > middle) { j--; };
116 //在middle右边找到一个比middle大的值
117 if (i == j) {break; }
118 //当i=j时,middle左边都是比middle小的数,右边都是比middle大的;跳出循环
119 nums[i] = nums[i] nums[j];
120 nums[j] = nums[i] - nums[j];
121 nums[i] = nums[i] - nums[j]; //两个值交换位置
122 if (nums[i] == nums[j]) { j--; }
123 //如果两个值相等,且等于middle,为避免进入死循环,j--
124 }
125 Sort(nums, left, i); //递归
126 Sort(nums, i 1, right);
127 }
128 }
129
130 //--------拉格朗日插值查找法(相同元素返回第一个元素下标)-----------------
131 public static int LaGeLangRi(int[] a, int key)
132 {
133 int tou=0;
134 int wei=a.Length-1;
135 int zhong =0;
136 while(tou<=wei)
137 {
138 zhong = tou (wei - tou) * (key - a[tou]) / (a[wei] - a[tou]);
139 if (key == a[zhong]) { break; }
140 else if (key > a[zhong]) { tou = zhong 1; }
141 else{wei=zhong-1;}
142 }
143 Console.Write(key); Console.WriteLine("---->对应的下标是:" zhong);
144 return zhong;
145
146 }
147 //-------------------二分查找法(相同元素返回第一个元素下标)------------------------
148 public static void Dichotomy(int[] array,int item)
149 {
150 int x = BinarySearch(array, 0, array.Length - 1, item);
151 Console.Write(item); Console.WriteLine("---->对应的下标是:" x);
152 }
153 public static int BinarySearch(int[] arr, int low, int high, int key)
154 {
155 int mid = (low high) / 2;
156 if (low > high){return -1;}
157 else
158 {
159 if (arr[mid] == key){ return mid;}
160 else if (arr[mid] > key){return BinarySearch(arr, low, mid - 1, key);}
161 else{return BinarySearch(arr, mid 1, high, key);}
162 }
163
164 }
165 }
166 }
备注:
排序的话,快速排序效率是较高的. 来源:http://www./content-4-75951.html
|