数据结构-----排序算法

选择排序

将要排序的数组分成两部分，一部分是从小到大已经排好序的，一部分是无序的，
从无序的部分取出最小的数值，放到已经排好序的部分的最后。

class ChooseSort{
 
    public static void sort(int[] arr){
        int t;
        for(int i=0;i<arr.length;i++){
            int m = i;
            for(int j=i+1;j<arr.length;j++){
                //如果 j 元素比 m 元素小，将 j 赋值给 m
                if(arr[j]<arr[m]){
                    m = j;
                }
            }
            //交换m 和 i 两个元素的位置
            if(i != m){
                t = arr[i];
                arr[i] = arr[m];
                arr[m] = t;
            }
        }
        System.out.println(Arrays.toString(arr));
    }
 
}

冒泡排序

从数组中扫描待排序的元素，扫描过程中依次对相邻元素进行比较，将数值大的元素后移。
每经过一趟排序后，数值最大的元素将移到末尾，此时加下该元素的位置，下一趟排序
只需要比较到此位置为止，直到所有元素都已有序排列

 class BubblingSort{
    public static void sort(int[] arr){
        int t;
        for (int i=0 ;i<arr.length;i++){
            //循环比较两个相邻元素的大小
            for (int j=0;j<arr.length-i-1;j++){
                //比较相邻元素大小，大的后移小的前移
                if(arr[j]>arr[j+1]){
                    t = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1]=t;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }
 
}

插入算法

将排序的数组分成两部分，每次从后面的数组部分中去除索引最小的数组元素，
插入到前面数组部分的适当位置中。通常在开始排序时，将数组的第一个元素
作为一组，后面的所有元素被当成一组。

class InsertSort{
    public static void sort(int[] arr){
        //把第一个元素看作一部分，第二个元素看作另一部分
        //从第二部分中一次取元素插入到第一部分中
        for(int i = 1;i<arr.length;i++){
            int temp = arr[i];
            int j = i - 1;
            //一次和 i 前面的元素比较，寻找合适的插入位置
            while (temp < arr[j]){
                arr[j+1] = arr[j];
                j--;
                if(j==-1){
                    break;
                }
            }
            //将插入元素插入到合适的位置
            arr[j+1] = temp;
        }
        System.out.println(Arrays.toString(arr));
    }
 
}

快速排序

被认为是最好的排序方式之一
基本思路为：将一个大的数组的排序问题，分解成两个小数组的排序
而每个小数组的排序又可以继续分解成更小的2个数组，这样一直递归分解下去，
直到数组的大小最大为2.

 class FastSort{
    public static int[] sort(int[] arr,int left,int right){
        int t;
        if(left<right){
            int s = arr[left];
            int i = left;
            int j = right+1;
            while (true){
                //向右找大于s的数的索引
                while (i+1<arr.length&&arr[++i]<s);
                //向左找小于s的数的索引
                while (j-i>-1 && arr[--j]>s);
                //如果 i>=j 退出循环
                if(i>=j){
                    break;
                }else {
                    //交换 i 和 j 位置的元素
                    t = arr[i];
                    arr[i] = arr[j];
                    arr[j] = t;
                }
            }
            arr[left] = arr[j];
            arr[j] = s;
            //对左边的数据进行递归
            sort(arr,left,j-1);
            //对右边的数据进行递归
            sort(arr,j+1,right);
        }
        return arr;
    }
}

测试

 
public class Sort {
    public static void main(String[] args) {
        int []arr = {10,7,8,5,2,4,7,3,1,6};
        //BubblingSort.sort(arr);
        //System.out.println(Arrays.toString(FastSort.sort(arr,0,9)));
        //ChooseSort.sort(arr);
        InsertSort.sort(arr);
    }
}