排序算法（一）（Java实现）

   本文主要介绍七种基本的排序算法：冒泡排序，快速排序，插入排序，希尔排序，选择排序，堆排序和归并排序。其中，快速排序是冒泡排序的增强，希尔排序是插入排序的增强，堆排序是选择排序的增强。

1、冒泡排序
原理：第一轮比较，将序列中的每个元素两两进行比较，小于则交换，直到比较到最后一个位置，相当于将第一轮将序列中最大的数放在了最后一个位置；第二轮，将序列中的每个元素（最后一个除外）两两比较，小于则交换，将这一轮中的最小值放到倒数第二个位置上，依次进行，直到剩下一个元素进行比较。
举例如下：
排序算法（一）（Java实现）
代码实现如下：

 public void swap(int[] arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
 public void BubbleSort(int[] arr){
        for(int i = 0;i < arr.length;i++){
            for(int j = 0;j < arr.length-1-i;j++){//注意循环边界条件
                if(arr[j] > arr[j+1]){
                    swap(arr,j,j+1);
                }
            }
        }
    }

2、插入排序
原理：将一个序列分为有序序列和无序序列，初始状态将第一个元素作为有序序列，其余元素为无序序列；将无序序列中的元素一次与有序序列中的元素进行排序，插入到合适位置，直到无序序列中的最后一个元素插入到有序序列中为止。
举例如下：
排序算法（一）（Java实现）
代码实现如下：

 public void insertSort(int[] arr){
        for(int i = 1;i < arr.length;i++) {//若a大于b，将b插入a前面，i要从下标为1处开始遍历
            if (arr[i] < arr[i - 1]) {
                int temp = arr[i];
                int j = i - 1;
                for (; j >= 0; j--) {
                    if (arr[j] > temp) {//将大于temp的往后移动
                        arr[j + 1] = arr[j];
                    }else{
                        break;
                    }
                }
                arr[j + 1] = temp;
            }
        }
    }

3、选择排序
原理：先将第一个元素与其余元素依次比较，若第一个元素大于第二个元素交换，再将第三个元素与第一个位置上元素进行比较，依此类推，第一轮后第一个位置上的元素是最小的，接着进行第二轮比较，等等，直到最后一个位置。
排序算法（一）（Java实现）
代码实现：

    public void chooseSort(int[] arr){
        for(int i = 0;i < arr.length;i++){
            //第一轮将最小的数放在最前面（每个数与第一个数比较，小则交换）；
            // 第二轮从第二位数开始比较，结果将这一轮中最小的数放在第二位置上，一次进行到最后一位
            for(int j = i+1;j < arr.length;j++){
                if(arr[j] < arr[i]){
                    swap(arr,j,i);
                }
            }
        }
}

排序算法（一）（Java实现）

相关推荐