排序算法集合

忘是亡心i 2022-05-23 08:49 115阅读 0赞

# 1.插入排序 #

> 从未排序的集合中找出一个元素，依次与已排序的集合元素进行比较，如果满足规则，小于或是等于，直接插入，依次循环，直至待排序集合元素为空。

`代码清单.插入排序`

/** * 直接插入排序 * @param arr */
        public void insertSort(int[] arr) {
            for(int i=1;i<arr.length;i++) {
                int j = i;
                while(j>0&&arr[j]<arr[j-1]) {
                    int temp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = temp;
                    j--;
                }
            }
        }

--------------------

# 2.选择排序 #

> 从待排序元素集合中，找出其中最大或是最小的元素，插入到集合的队首位置。

`代码清单.选择排序`

/** * 选择排序 每次选择最小的或者是最大的插入到队首 * @param arr */
        public void selectSort(int[] arr) {
            for(int i=0;i<arr.length;i++) {
                int min = i;
                for(int j = i+1;j<arr.length;j++) {
                    if(arr[j]<arr[min]) {
                        min = j;
                    }
                }
    
                if(min!=i) {
                    int t = arr[min];
                    arr[min] = arr[i];
                    arr[i] = t;
                }
            }
        }

--------------------

# 3.冒泡排序 #

> 冒泡排序的原则，每次循环查找，找出元素最小或是最大的元素到末尾的位置，类似气泡一样，将小的浮出水面，将大的沉至最底下。

`代码清单.冒泡排序`

public void bubbleSort(int[] arr) {
            boolean isExchange = true;
            for(int i=0;i<arr.length&&isExchange;i++) {
                for(int j=1;j<arr.length-i-1;j++) {
                    if(arr[j-1] <= arr[j]) {
                        isExchange = false;
                    }else {
                        int temp = arr[j-1];
                        arr[j-1] = arr[j];
                        arr[j] = temp;
                        isExchange = true;
                    }
                }
            }
        }

注意上述使用了一个`isExchange`变量对排序算法进行了优化，初始的时候设置为true代表的是需要进行交换，当我们排序一圈发现每次都是arr\[j-1\] <= arr\[j\] 成立，那么代表集合已经排序，无序再进行循环，可以提前结束循环。

--------------------

# 4.快速排序 #

> 快速排序的原理是，先找出一个基数位，然后对集合进行前后同时扫描，将基数大的放在右边，比基数小的放在左边，不停的迭代，直至排序完成。

`代码清单.快速排序`

public void quicksort(int[] arr,int left,int right) {
            int i=left,j=right,temp;
            if(left > right) {
                return ;
            }
            temp = arr[left];//哨兵
            while(i!=j) {
                while(arr[j] > temp&& i<j) {
                    j--;
                }
                while(arr[i] <=temp && i<j) {
                    i++;
                }
                if(i<j) {
                    int t = arr[i];
                    arr[i] = arr[j];
                    arr[j] = t;
                }
            }
            arr[left] = arr[i];
            arr[i] = temp;
            quicksort(arr,left,i-1);
            quicksort(arr,i+1,right);
        }

--------------------

# 5.希尔排序 #

> 希尔排序的原理是：先将待排序的集合元素通过设置增量的方式进行分组，然后对每个分组进行交换，或者是插入的方式让每个小组变的有序，直至增量为1排序完毕。下面给出两种实现方式：

`代码清单.交换方式`

public static void shellSort(int arr[]) {
            for(int gap = arr.length/2;gap>0;gap=gap/2) {
            //gap设置的增量
                for(int i=gap;i<arr.length;i++) {
                    int j = i;
                    while(j-gap>0&&arr[j]<arr[j-gap]) { //交换操作
                        int temp = arr[j];
                        arr[j] = arr[j-gap];
                        arr[j-gap] = temp;
                        j-=gap;
                    }
                }
            }
        }

`代码清单.移位操作`

public static void shell_move_sort(int[] arr) {
            for(int gap = arr.length/2;gap>0;gap = gap/2) {
                for(int i=gap;i<arr.length;i++) {
                    int j = i;
                    int temp = arr[j];
                    if(arr[j]< arr[j-gap]) {
                    //这里类似插入排序的方式，元素插入到该分组中合适的位置
                        while(j-gap>=0&& temp<arr[j-gap]) {
                            arr[j] = arr[j-gap];
                            j -=gap;
                        }
                        arr[j] = temp;
                    }
                }
            }
        }