哥们,为了写这个破狗屎,我屁股一下午没动地方了= =!(其中递归那个地方还是不理解的)只不过用程序单调实现的- using System;
- using System.Collections.Generic;
- using System.Linq;
- using System.Text;
- using System.Threading.Tasks;
- namespace 快速排序
- {
- class Program
- {
- /// <summary>
- /// 现学现卖
- /// </summary>
- /// <param name="args"></param>
- static void Main(string[] args)
- {
- int[] s = new int[] { 72, 6, 57, 88, 60, 42, 83, 73, 48, 85 };
- //int[] s = new int[] { 32, 21, 47,37 };
- QuikSort(s, 0, s.Length - 1);
- for (int i = 0; i < s.Length; i++)
- {
- Console.WriteLine(s[i]);
- }
- }
- //快分就是以数组s[0]为基数key,从右面开始找到s[j ]比key小的填到s[0],再从左面s[1]找到s[i]比key大 填到s[j]
- //从右面s[j-1]找到新s[j] 比key小的填到s[i],再从左面s[i+1]找到新s[i] 比key大 填到s[j]
- //知道i 和 j碰上了 那么说明 左面没有比key大的 右面没有比key小的
- //关键点在于找到的同时,放到另一侧
-
- //这个方法是把数组以key为基数,分成两部分,左面比key小,右面比key大
-
- //并返回分组后,key的新下标,注意key为s【le】
- public static int FindKeyIndex(int[] s, int le, int rg)//le,rg都是数组下标
- {
- int k = 0;//用于返回的key的坐标
- int key = s[le];//每次都默认s[le]为key 相当于把这个位置空出来
- int i = le;//i代表从前往后找 找比key大的
- int j = rg;//j代表从后往前找 找比key小的
-
- while (i < j)//如果就1个数,没必要排序
- {
- //首先一定要从右往左找
- while (true)
- {
- //这个if一定要写
- //开始我没写,结果有一个数排序错误,当i=3,j=4的时候,
- //s[4]确实大于s[3] 结果j--了
- //判断s[3]=key,i++了
- //导致i比j大 做了后面的从左往右找
- //这就和i与j相遇 停止查找 这个事实矛盾了,后续情况没再跟进
- if (i == j)
- {
- break;
- }
- if (s[j] <= key)
- {
- s[i] = s[j];
- i++;
- break;
- }
- else
- {
- j--;
- }
- }
- //从左往右找
- while (true)
- {
- if (i == j)
- {
- break;
- }
- if (s[i] >= key)
- {
- s[j] = s[i];
- j--;
- break;
- }
- else
- {
- i++;
- }
- }
- }
- s[i] = key;
- k = i;
- return k;//这个下标是用来进行接下来以k 为基准的左右两面的排序
- }
- //递归排序数组
- public static void QuikSort(int[] s, int le, int rg)
- {
- if (le < rg)//如果数组中就一个元素,也不用排了
- {
- int index = FindKeyIndex(s, le, rg);
- if (index - 1 != 0)//如果index==1,那左面不用排了
- {
- QuikSort(s, le, index - 1);
- }
- if (index + 1 < rg)//如果index右面也剩下一个,也不用排了
- {
- QuikSort(s, index + 1, rg);
- }
- }
- }
- }
- }
复制代码 |