java.数据结构.快速排序.学习笔记

港控/mmm° 2022-09-01 08:13 141阅读 0赞

### 快速排序 ###

*   *  普通排序中位数算法
     *  位置调整
     *  核心算法（左右对应调换）
     *  递归结束条件判断
     *  递归部分
     *  总代码

## 普通排序中位数算法 ##

**进行快速排序的第一步是选择适当的轴(pivot)作为整个算法的基准数，这个轴最好是应该是一个相对处于中间的数。为了使算法更简便，我们极力避免取这个数组中最极端(最大或最小)的数字。  
一般的，我们选取三个数出来，取这三个数的中位数作为轴，这样使作为轴的数不可能是极端的数字。为方便起见，我们一般选择数组两端和正中间数字进行比较，选取其中的中位数。**

int mid = (max+min)/2;
            int temp;
            //将这三个数字进行隔空排序，选出中间的数字
            for(;;)
            { 
                if(a[max]>=a[mid]&&a[mid]>=a[min])
                { 
                    break;
                }
                if(a[max]<a[mid])
                { 
                    temp = a[max];
                    a[max] = a[mid];
                    a[mid] = temp;
                }
                if(a[mid]<a[min])
                { 
                    temp = a[mid];
                    a[mid] = a[min];
                    a[min] = temp;
                }
                if(a[min]>a[max])
                { 
                    temp = a[min];
                    a[min] = a[max];
                    a[max] = temp;
                }
            }

初始的情况:305 65 7 90 120 110 8  
结束的状态:8 65 7 90 120 110 305  
然后我们使轴对应a\[mid\]的值。此时a\[min\],a\[max\]以及成为轴的a\[mid\]的位置相对正确，在排序过程中可以不与关注。  
**为减少轴的移动次数（轴的移动次数过多对算法产生不好的影响），我们将a\[mid\]和a\[max-1\]的位置进行调换（之后再换回来）**

## 位置调整 ##

//稍微调整一下位置
            int pivot = a[mid];//先设置基准位; 
            temp = a[max-1];
            a[max-1] = a[mid];
            a[mid] = temp;

初始的情况：8 65 7 90 120 110 305  
结束的状态: 8 65 7 110 120 90 305  
然后开始算法的核心部分，遇见比pivot小的数放到相对前面，比pivot大的数放到相对后面。

## 核心算法（左右对应调换） ##

//开始
            int left = min+1;
            int right = max-2;
            while(left<right)
            { 
                //先考虑左边(远的一边)
                while(a[left]<pivot&&left<right)
                { 
                    left++;
                }
                //再考虑右边
                while(a[right]>pivot&&left<right)
                { 
                    right--;
                }
                if(right>left)
                { 
                    temp = a[left];
                    a[left] = a[right];
                    a[right] = temp;
                }
            }

然后再将轴换回来

a[max-1] = a[left];
            a[left] = pivot;

开始的情况： 8 65 7 110 120 90 305  
结束的状态： 8 65 7 90 110 120 305  
***注意！！！！！！！！***  
这是一个递归算法，在后面我们递归的步骤，所以递归的结束条件要先明确

## 递归结束条件判断 ##

if(max<min||max-min<=2)
            { 
                return;
            }

**值得一提的是max-min<=2指当需要排序的数字少于三个，我们不用到核心算法步骤就可以排序完毕，即只使用前面的普通排序取中位数算法。**

## 递归部分 ##

quickSort(a, min, left-1);
            quickSort(a, left+1, max);

## 总代码 ##

public class TestA  
    { 
        public static void main(String[] arg)
        { 
            int [] a = { 305,65,7,90,120,110,8};
            quickSort(a,0,a.length-1);
            for(int i=0;i<a.length;i++)
            { 
                System.out.print(a[i]+" ");
            }
        }
        public static void quickSort(int a[],int min,int max)
        { 
            int mid = (min+max)/2;
            for(;;)
            { 
                if(a[max]>=a[mid]&&a[mid]>=a[min])
                { 
                    break;
                }
                if(a[min]>=a[mid])
                { 
                    exchange(a, min, mid);
                }
                if(a[mid]>=a[max])
                { 
                    exchange(a, mid, max);
                }
                if(a[min]>=a[max])
                { 
                    exchange(a, min, max);
                }
            }
            if(min>max||max-min<=2)
            { 
                return;
            }
            int pivot = a[mid];
            exchange(a, mid, max-1);
            int left = min+1;
            int right = max-2;
            while(right>left)
            { 
                while(a[left]<pivot&&right>left)
                { 
                    left++;
                }
                while(a[right]>pivot&&right>left)
                { 
                    right--;
                }
                if(right>left)
                { 
                    exchange(a, right, left);
                }
            }
            exchange(a, left, max-1);
            quickSort(a, left+1, max);
            quickSort(a, min, left-1);
        }
        public static void exchange(int [] a, int b, int c)
        { 
            int temp = a[b];
            a[b] = a[c];
            a[c] = temp;
        }
    }