C# 递归式快速排序算法

  1 static void Main(string[] args)
  2         {
  3 
  4             Console.WriteLine("************快速排序*****************");
  5             int[] list = new int[] { 4, 7, 6, 5, 3, 2, 8, 1 };
  6             QuickSort qs = new QuickSort();
  7             qs.quikSort(list, 0, list.Length - 1);
  8             for (int i = 0; i < list.Length; i++)
  9             {
 10                 Console.WriteLine("第{0}位是{1}", i + 1, list[i]);
 11             }
 12             // Console.WriteLine(list);
 13 
 14             Console.ReadKey();
 15         } 68 
 69 
 70     //递归快速排序法
 71     public class QuickSort
 72     {
 73         //快速排序
 74         public  void quikSort(int[] arr, int startIndex, int endIndex)
 75         {
 76             //递归结束条件  startIndex>endIndex
 77             if (startIndex >= endIndex)
 78             {
 79                 return;
 80             }
 81 
 82             //得到基准元素的位置
 83             int pivotIndex = partiton(arr, startIndex, endIndex);
 84 
 85             //根据基准元素，分成两部分递归排序
 86             quikSort(arr, startIndex, pivotIndex - 1);
 87             quikSort(arr, pivotIndex + 1, endIndex);
 88         }
 89 
            //指针交换法
 90         private static int partiton(int[] arr, int startIndex, int endIndex)
 91         {
 92             //取第一个位置的元素作为基准元素
 93             int pivot = arr[startIndex];
 94             int left = startIndex;
 95             int right = endIndex;
 96 
 97             while (left != right)
 98             {
 99                 //控制right指针比较并左移
100                 while (left < right && arr[right] > pivot)
101                 {
102                     right--;
103                 }
104 
105                 //控制right指针比较并右移
106                 while (left < right && arr[left] <= pivot)
107                 {
108                     left++;
109                 }
110 
111                 //交换left和right指向的元素
112                 if (left < right)
113                 {
114                     int p = arr[left];
115                     arr[left] = arr[right];
116                     arr[right] = p;
117                 }
118             }
119 
120             //pivoe和指针重合点交换
121             int s = arr[left];
122             arr[left] = arr[startIndex];
123             arr[startIndex] = s;
124 
125             return left;
126         }
127

//挖坑法
        private static int partiton1(int[] arr, int startIndex, int endIndex)
        {
            // 4, 7, 6, 5, 3, 2, 8, 1 
            //获取第一个位置的元素作为基准元素
            int pivot = arr[startIndex];  //4
            int left =startIndex;   //0
            int right = endIndex;   //7

            //坑的位置，初始等于pivot的位置
            int index = startIndex;  //0

            //大循环在左右指针重合或交错时结束
            while (right >= left)
            {
                //right指针从右向左进行比较
                while (right >= left)
                {
                    int a = arr[right];
                    if (arr[right] < pivot)
                    {
                        int s = arr[right];
                        int t = arr[left];

                        arr[left] = arr[right];
                        index = right;
                        left++;
                        break;
                    }
                    right--;
                }

                //left指针从左向右进行比较
                while (right > left)
                {
                    if (arr[left] >= pivot)
                    {
                        int a = arr[right];
                        int b = arr[left];

                        arr[right] = arr[left];
                        index = left;
                        right--;
                        break;
                    }
                    left++;

                }
            }

            arr[index] = pivot;
            return index;
        }

128     }