算法-快速排序

1.数组array，和整数num，把小于等于num的数放在数座左边，大于num的数放在数组右边。要求额外空间复杂度O(1),时间复杂度O(N)

 public void CodeShow()
        {
            int[] arr={1,3,5,2,3,2,3,4,2,3,1,4};
            int num=3;
​
            int index=0;
            int change=0;
            for (int i = 0; i < arr.Length; i++)
            {
                if(arr[i]<=num){
                    change=arr[i];
                    arr[i]=arr[index];
                    arr[index]=change;
                    index++;                   
                }
            }
            for(int i=0;i<arr.Length;i++)
            {
              Console.WriteLine("结果：{0}",arr[i]);
            }        
        }

2.上一个数组要求左边小于num，中间等于num，右侧大于num。（荷兰国旗问题）

 public void CodeShow_2()
        {
            int[] arr={1,3,5,2,3,2,3,4,2,3,1,4};
            int num=3;
​
            int indexMin=0;
            int indexMax=arr.Length-1;
            int change=0;
​
            for (int i = 0; i <= indexMax; i++)
            {
                if (arr[i]<num)
                {
                    change=arr[i];
                    arr[i]=arr[indexMin];
                    arr[indexMin]=change;
                    indexMin++;
                    continue;
                }
                if (arr[i]>num)
                {
                    change=arr[i];
                    arr[i]=arr[indexMax];
                    arr[indexMax]=change;
                    indexMax--;
                    i--;
                }
            }
            for(int i=0;i<arr.Length;i++)
            {
              Console.WriteLine("结果：{0}",arr[i]);
            }     
        }

3.数组arr ，快速排序。

方法一：

public void CodeShow_3()
        {
            int[] arr={1,3,5,2,3,2,3,4,2,3,1,4};
           
            sorting(ref arr,0,arr.Length-1);
​
            for(int i=0;i<arr.Length;i++)
            {
              Console.WriteLine("---------结果：{0}",arr[i]);
            }     
​
        }
​
​
        public void sorting(ref  int[] array,int l ,int r)
        {
            if(l>=r)return;
            int m= process(ref array,l,r);        
            sorting(ref array,l,m-1);
            sorting(ref array,m+1,r);
        }    
        protected int process(ref int[] array,int l ,int r)
        {            
            int indexMin=l;
            int indexMax=r-1;
            int change=0;
            int index=l;
​
            while (index<=indexMax)
            {
                if (array[index]<=array[r])
                {
                    change=array[index];
                    array[index]=array[indexMin];
                    array[indexMin]=change;
​
                    indexMin++;
                    index++;
                    continue;
                }
                if (array[index]>array[r])
                {
                    change=array[index];
                    array[index]=array[indexMax];
                    array[indexMax]=change;
                    indexMax--;
                    //index++;
                }
            }
                   change=array[r];
                    array[r]=array[indexMin];
                    array[indexMin]=change;
            return indexMin;
        }

快速排序方法二：

 public void  CodeShow_4()
        {
            int[] arr={1,3,5,2,3,2,3,4,2,3,1,4};
           
            sorting2(ref arr,0,arr.Length-1);
​
            ShowArr(arr);   
         
        }
        public void sorting2(ref  int[] array,int l ,int r)
        {
            if(l>=r)return;
            int[] m= process2(ref array,l,r);                
            sorting2(ref array,l,m[0]-1);
            sorting2(ref array,m[1]+1,r);
        }    
       protected int[] process2(ref int[] array,int l ,int r)
        {            
            int indexMin=l;
            int indexMax=r-1;
            int change=0;
            int index=l;
​
            while (index<=indexMax)
            {
                if (array[index]<array[r])
                {
                    change=array[index];
                    array[index]=array[indexMin];
                    array[indexMin]=change;
​
                    indexMin++;
                    index++;
                    continue;
                }
                if (array[index]>array[r])
                {
                    change=array[index];
                    array[index]=array[indexMax];
                    array[indexMax]=change;
                    indexMax--;
                    //index++;
                }
                if(array[index]==array[r])
                {
                    index++;
​
                }
            }
                   change=array[r];
                    array[r]=array[indexMax+1];
                    array[indexMax+1]=change;
            return  new  int[2]{indexMin,indexMax+1};
        }

方法三：方法一和二中比较数都是arr[r] ，将r位置变为随机位置，可降低复杂度。