冒泡排序，选择排序，插入排序，快速排序

红太狼 2022-01-06 20:17 454阅读 0赞

1 using System;
      2 using System.Collections.Generic;
      3 using System.Linq;
      4 using System.Text;
      5 using System.Data;
      6 
      7 namespace TestSample
      8 {
      9 
     10     #region explaination
     17 
     18 
     19     //一、冒泡排序 
     20 
     21     //已知一组无序数据a[1]、a[2]、……a[n]，需将其按升序排列。首先比较a[1]与a[2]的值，若a[1]大于a[2]则交换两者的值，否则不变。再比较a[2]与a[3]的值，若a[2]大于a[3]则交换两者的值，否则不变。再比较a[3]与a[4]，依此类推，最后比较a[n-1]与a[n]的值。这样处理一轮后，a[n]的值一定是这组数据中最大的。再对a[1]~a[n-1]以相同方法处理一轮，则a[n-1]的值一定是a[1]~a[n-1]中最大的。再对a[1]~a[n-2]以相同方法处理一轮，依此类推。共处理n-1轮后a[1]、a[2]、……a[n]就以升序排列了。 
     22     
     23     //优点：稳定，比较次数已知； 它的时间复杂度为O（n^2）
     24 
     25     //缺点：慢，每次只能移动相邻两个数据，移动数据的次数多。 
     26 
     27 
     28     //二、选择排序 
     29 
     30     //已知一组无序数据a[1]、a[2]、……a[n]，需将其按升序排列。首先比较a[1]与a[2]的值，若a[1]大于a[2]则交换两者的值，否则不变。再比较a[1]与a[3]的值，若a[1]大于a[3]则交换两者的值，否则不变。再比较a[1]与a[4]，依此类推，最后比较a[1]与a[n]的值。这样处理一轮后，a[1]的值一定是这组数据中最小的。再将a[2]与a[3]~a[n]以相同方法比较一轮，则a[2]的值一定是a[2]~a[n]中最小的。再将a[3]与a[4]~a[n]以相同方法比较一轮，依此类推。共处理n-1轮后a[1]、a[2]、……a[n]就以升序排列了。 
     31     //总是假设a【a1】最小
     32     //每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法
     33 
     34     //优点：不稳定，比较次数与冒泡排序一样，数据移动次数比冒泡排序少； 它的时间复杂度为O（n^2）
     35 
     36     //缺点：相对之下还是慢。 
     37 
     38     //三、插入排序 
     39 
     40     //假定这个数组的序是排好的，然后从头往后，如果有数比当前外层元素的值大，则将这个数的位置往后挪，直到当前外层元素的值大于或等于它前面的位置为止.这具算法在排完前k个数之后，可以保证a[1…k]是局部有序的，保证了插入过程的正确性.
     41 
     42     //优点：稳定，快；  O(n^2)
     43 
     44     //缺点：比较次数不一定，比较次数越少，插入点后的数据移动越多，特别是当数据总量庞大的时候，但用链表可以解决这个问题。 
     45 
     46     //四、缩小增量排序 
     47 
     48     //由希尔在1959年提出，又称希尔排序。 
     49 
     50     //已知一组无序数据a[1]、a[2]、……a[n]，需将其按升序排列。发现当n不大是，插入排序的效果很好。首先取一增量d(d <n)，将a[1]、a[1+d]、a[1+2d]……列为第一组，a[2]、a[2+d]、a[2+2d]……列为第二组……，a[d]、a[2d]、a[3d]……列为最后一组依此类推，在各组内用插入排序，然后取d' <d，重复上述操作，直到d=1。 
     51 
     52     //优点：快，数据移动少； 
     53 
     54     //缺点：不稳定，d的取值是多少，应取多少个不同的值，都无法确切知道，只能凭经验来取。 
     55 
     56     //五、快速排序 
     57 
     58     //快速排序是冒泡排序的改进版，是目前已知的最快的排序方法。 
     59 
     60     //设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。
     61 
     62     //优点：极快，数据移动少；O(nlog n) 期望时间，O(n^2) 最坏情况 
     63 
     64     //缺点：不稳定。 
     65 
     66     #endregion
     67 
     68     class Program
     69     {
     70         /// <summary>
     71         /// bubble sort
     72         /// </summary>
     73         /// <param name="array"></param>
     74         static void Bsort(int[] array)
     75         {
     76             //int[] bsort = { 12, 35, 11, 67, 34, 89, 99, 23 };
     77             for (int i = 0; i < array.Length; i++)
     78             {
     79                 for (int j = i + 1; j < array.Length; j++)
     80                 {
     81                     if (array[j] < array[i])
     82                     {
     83                         int temp;
     84                         temp = array[j];
     85                         array[j] = array[i];
     86                         array[i] = temp;
     87 
     88                     }
     89                 }
     90             }
     91             Console.WriteLine("after the bubble sort, the array as below:");
     92             for (int i = 0; i < array.Length; i++)
     93             {
     94                 Console.Write(array[i] + " ");
     95             }
     96  
     97         }
     98 
     99         /// <summary>
    100         /// select sort
    101         /// </summary>
    102         /// <param name="array"></param>
    103         static void SelectSort(int[] array)
    104         {
    105             for (int i = 0; i < array.Length; i++)
    106             {
    107                 int temp;
    108                 int min = array[i];
    109                 for (int j = i + 1; j < array.Length; j++)
    110                 {
    111                     if (min > array[j])
    112                     {
    113                         min = array[j];
    114                         temp = array[i];
    115                         array[i] = array[j];
    116                         array[j] = temp;
    117                     }
    118                 }
    119             }
    120             Console.WriteLine("after the select sort, the array as below:");
    121             for (int i = 0; i < array.Length; i++)
    122             {
    123                 Console.Write(array[i] + " ");
    124             }
    125         }
    126 
    127         /// <summary>
    128         /// insert sort
    129         /// </summary>
    130         /// <param name="array"></param>
    131 
    132         static void Isort(int[] array)
    133         {
    134             int temp;
    135             for (int i = 1; i < array.Length; i++)
    136             {
    137                 temp = array[i];
    138                 int j = i;
    139                 while (j > 0 && array[j - 1] > temp)
    140                 {
    141                     array[j] = array[j - 1];
    142                     j--;
    143                 }
    144                 array[j] = temp;
    145 
    146             }
    147             Console.WriteLine("after the Insert sort,the array as below:");
    148 
    149             for (int i = 0; i < array.Length; i++)
    150             {
    151                 Console.Write(array[i] + " ");
    152             }
    153         }
    154 
    155         static void QuickSort(int[] array,int left,int right)
    156         {
    157             //左边索引小于右边，则还未排序完成
    158             if (left < right)
    159             {
    160                 //取中间的元素作为比较基准，小于他的往左边移，大于他的往右边移
    161                 int middle = array[(left + right) / 2];
    162                 int i = left - 1;
    163                 int j = right + 1;
    164                 while (true)
    165                 {
    166                     while (array[++i] < middle && i < right) ;
    167                     while (array[--j] > middle && j > 0) ;
    168                     if (i >= j)
    169                         break;
    170                     //Swap(numbers, i, j);
    171                     int temp = array[i];
    172                     array[i] = array[j];
    173                     array[j] = temp;
    174                 }
    175                 QuickSort(array, left, i - 1);
    176                 QuickSort(array, j + 1, right);
    177             }
    178 
    179 
    180 
    181         }
    182 
    183         static void Main(string[] args)
    184         {
    185             int[] array = new int[10];
    186             List<int> list=new List<int>();
    187             Random rd=new Random();
    188 
    189             for(int i=0;i<10;i++)
    190             {
    191                 int next=rd.Next(1,100);
    192                 if (!list.Contains(next))
    193                 {
    194                     list.Add(next);
    195                 }
    196             }
    197 
    198             array = list.ToArray();
    199 
    200             Bsort(array);
    201             Console.WriteLine();
    202             SelectSort(array);
    203             Console.WriteLine();
    204             Isort(array);
    205             Console.WriteLine();
    206             QuickSort(array,0,array.Length-1);
    207             Console.WriteLine("after the quick sort,the array as below:");
    208 
    209             for (int m = 0; m < array.Length; m++)
    210             {
    211                 Console.Write(array[m] + " ");
    212             }    
    213 
    214         }
    215     }    
    216 }

转载于:https://www.cnblogs.com/Jenny90/archive/2013/04/13/3018401.html