C#算法基础之快速排序

  1 using System;
  2 using System.Collections.Generic;
  3 using System.Linq;
  4 using System.Text;
  5 using System.Threading.Tasks;
  6 
  7 namespace ConsolePractice
  8 {
  9     class CArray
 10     {
 11         private int[] arr;
 12         //数组大小
 13         private int upper;
 14         //下标
 15         private int numElements;
 16 
 17         /// <summary>
 18         /// 初始化数组参数
 19         /// </summary>
 20         /// <param name="size"></param>
 21         public CArray(int size)
 22         {
 23             arr = new int[size];
 24             upper = size - 1;
 25             numElements = 0;
 26         }
 27 
 28         /// <summary>
 29         /// 插入方法
 30         /// </summary>
 31         /// <param name="item">存储的数</param>
 32         public void Insert(int item)
 33         {
 34             arr[numElements] = item;
 35             numElements++;
 36         }
 37 
 38         /// <summary>
 39         /// 输出方法
 40         /// </summary>
 41         public void DisplayElements()
 42         {
 43             for (int i = 0; i <= upper; i++)
 44             {
 45                 Console.Write(arr[i] + " ");
 46             }
 47             Console.WriteLine();
 48         }
 49 
 50         /// <summary>
 51         /// 清除数组
 52         /// </summary>
 53         public void Clear()
 54         {
 55             for (int i = 0; i <= upper; i++)
 56             {
 57                 arr[i] = 0;
 58             }
 59             numElements = 0;
 60         }
 61 
 62         #region 快速排序算法
 63         /// <summary>
 64         /// 快速排序算法
 65         /// </summary>
 66         public void QSort()
 67         {
 68             RecQSort(0, numElements - 1);
 69         }
 70 
 71         public void RecQSort(int first, int last)
 72         {
 73             if ((last - first) <= 0)
 74                 return;
 75             else
 76             {
 77                 int part = this.Partition(first, last);
 78                 RecQSort(first, part - 1);
 79                 RecQSort(part + 1, last);
 80             }
 81         }
 82 
 83         public int Partition(int first, int last)
 84         {
 85             int pivotVal = arr[first];
 86             int theFirst = first;
 87             bool okSide;
 88             first++;
 89             do
 90             {
 91                 okSide = true;
 92                 while (okSide)
 93                 {
 94                     if (arr[first] > pivotVal)
 95                         okSide = false;
 96                     else
 97                     {
 98                         first++;
 99                         okSide = (first <= last);
100                     }
101                 }
102                 okSide = true;
103                 while (okSide)
104                 {
105                     if (arr[last] <= pivotVal)
106                         okSide = false;
107                     else
108                     {
109                         last--;
110                         okSide = (first <= last);
111                     }
112                 }
113                 if (first < last)
114                 {
115                     Swap(first, last);
116                     this.DisplayElements();
117                     first++;
118                     last--;
119                 }
120 
121             } while (first <= last);
122             Swap(theFirst, last);
123             this.DisplayElements();
124             return last;
125         }
126 
127         public void Swap(int item1, int item2)
128         {
129             int temp = arr[item1];
130             arr[item1] = arr[item2];
131             arr[item2] = temp;
132         }
133         #endregion
134     }
135 
136     class C_shape
137     {
138         static void Main()
139         {
140             CArray nums = new CArray(10);
141             Random rnd = new Random(100);
142             for (int i = 0; i < 10; i++)
143             {
144                 nums.Insert(rnd.Next(0, 100));
145             }
146             Console.WriteLine("Before sorting:");
147             nums.DisplayElements();
148             Console.WriteLine("During sorting:");
149             nums.QSort();
150             Console.WriteLine("After sorting:");
151             nums.DisplayElements();
152             Console.ReadKey();
153         }
154     }
155 }