• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

C#递归式快速排序算法

原作者: [db:作者] 来自: [db:来源] 收藏 邀请
  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     }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap