1.冒泡排序
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace 排序算法练习 { /// <summary> /// 冒泡排序 /// /// 冒泡排序算法的运作如下：（从后往前） ///比较相邻的元素。如果第一个比第二个大，就交换他们两个。 ///对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。 ///针对所有的元素重复以上的步骤，除了最后一个。 ///持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。 /// /// 冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。 /// 所以，如果两个元素相等，我想你是不会再无聊地把他们俩交换一下的；如果两个相等的元素没有相邻，那么即使通 /// 过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种 /// 稳定排序算法。 /// /// 1.每两个数进行比较，需要2层循环比较 /// 2.最后一次比较容易出现超出数组范围的错误 /// /// </summary> class BubbleSort : SortBase { public BubbleSort(int[] array,string name) : base(array) { Console.WriteLine("Init Bubble Array OK,name " + name); } /// <summary> /// 从小排序 /// </summary> public override void MinSort() { for(int i = 1; i < tempArray.Length; i++) { for(int j = tempArray.Length - 1; j >=i; j--) { if(tempArray[j] < tempArray[j-1]) { int temp = tempArray[j]; tempArray[j] = tempArray[j - 1]; tempArray[j - 1] = temp; counter++; } } } } public override void MaxSort() { for (int i = 1; i < tempArray.Length; i++) { for (int j = tempArray.Length - 1; j >= i; j--) { if (tempArray[j] > tempArray[j - 1]) { int temp = tempArray[j]; tempArray[j] = tempArray[j - 1]; tempArray[j - 1] = temp; counter++; } } } } public override void Display() { foreach(var item in tempArray) { Console.WriteLine("Sorted Element = {0}",item); } Console.WriteLine("循环次数 counter = {0}", counter); } } } 2.选择排序 using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace 排序算法练习 { /// <summary> /// 选择排序 /// /// 选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小 /// （或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方 /// 法（比如序列[5， 5， 3]第一次就将第一个[5]与[3]交换，导致第一个5挪动到第二个5后面）。 /// </summary> class SelectionSort : SortBase { private int minIndex = 0; private int temp; public SelectionSort(int[] array) : base(array) { Console.WriteLine("Init SelectionSort OK"); } public override void MinSort() { for(int i = 0; i < tempArray.Length-1; i++) { minIndex = i; for(int j = i+1; j < tempArray.Length;j++) { if(tempArray[j] < tempArray[minIndex]) { minIndex = j; counter++; } } temp = tempArray[i]; tempArray[i] = tempArray[minIndex]; tempArray[minIndex] = temp; } } public override void MaxSort() { } public override void Display() { foreach(var item in tempArray) { Console.WriteLine("Sort Element = " + item); } Console.WriteLine("循环次数 counter " + counter); } } }3.快速排序 using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace 排序算法练习 { /// <summary> /// 设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。 ///一趟快速排序的算法是： ///1）设置两个变量i、j，排序开始的时候：i=0，j=N-1； ///2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]； ///3）从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j] 和A[i]互换； ///4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i] 和A[j]互换； ///5）重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A[j] 不小于key,4中A[i] 不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。 /// </summary> class QuickSort : SortBase { public QuickSort(int[] array):base(array) { Console.WriteLine("Quick Sort Init OK"); } public override void Display() { foreach (var item in tempArray) { Console.WriteLine("Sorted Element = {0}", item); } } public override void MaxSort() { //Sort2 } public override void MinSort() { Sort3(this.tempArray,0,this.tempArray.Length-1); } int number = 0; #region 方案一 private int SortUnit(int[] array, int left, int right) { //默认key的左边都是放小于key的数 //key的右边都是放大于key的数 int key = array[left];//找到本次数组以left为索引的值作为key,用来分割数组成2部分 while (true) { //从右往左找到小于key的值统统放到key的左边 while (array[right] >= key && right > left) right--; array[left] = array[right]; //从左往右找到大于key的值统统放到key的右边 while (array[left] <= key && right > left) left++; array[right] = array[left]; if (right == left) break; } //right==left,去一个索引存放key array[left] = key;// number++; Console.WriteLine("第{0}次排序", number); foreach (int i in array) { Console.Write("{0}\t", i); } Console.WriteLine(); return right; } private void Sort(int[] array, int left, int right) { if (left >= right) return; int index = SortUnit(array,left, right); if(index-1 > left) Sort(array,left,index-1); if(index + 1 < right) Sort(array, index + 1, right); } #endregion #region 方案2：方案1的简化版 void Sort2(int[] nums, int left, int right) { int i = left; int j = right; int key = nums[left]; while (i < j) { while (i < j && nums[j] >= key) j--; nums[i] = nums[j]; while (i < j && nums[i] <= key) i++; nums[j] = nums[i]; } nums[i] = key; if(i-1 > left)Sort2(nums, left, i - 1); if(j+1 < right)Sort2(nums, j + 1, right); } #region 方案3 void Sort3(int[] nums, int left, int right) { //2,4,3,1,2 int i = left; int j = right; int key = nums[left]; while(true) { while (i < j && nums[j] > key) j--;//检测是否右边的数都大于key while (i < j && nums[i] < key) i++;//检测是否左边的数都小于key if (i == j) break;//i和j相等的时候为指向同一个数，退出循环 //不符合的两个数进行替换 int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; //如果出现替换过后的两个数还是相等，强制进入下个数的计算 if (nums[i] == nums[j]) j--; } if(i-1 > left) Sort3(nums, left, i - 1);//计算左边的数列 if(j+1 < right) Sort3(nums,j+1,right);//计算右边的数列 } } }
