八大排序算法

一、八大排序算法

[TOC]

1.冒泡排序

画图技术不到位,等找到好的画图工具再来补齐后面的图吧！

//冒泡排序
public static void bubbleSort(int[] arr) {
    if(arr == null || arr.length < 2) {
        return;//传入的数组为空或者长度小于2直接返回
    }
    for(int i = arr.length - 1; i > 0; i--) {
        for(int j = 0; j < i; j++) {  
            if(arr[j] > arr[j + 1]) {//两两进行比较
                swap(arr,j,j + 1);//若前面的数比后面的大,交换这两个数
            }
        }
    }
}
public static void swap(int[] arr, int j, int i) {
    //		int temp = arr[j];
    //		arr[j] = arr[i];
    //		arr[i] = temp;
    arr[i] = arr[i] ^ arr[j];
    arr[j] = arr[i] ^ arr[j];
    arr[i] = arr[i] ^ arr[j];
}

2.选择排序

public static void selectSort(int[] arr) {
    if(arr == null || arr.length < 2) {
        return;
    }
    for(int i = 0; i < arr.length - 1; i++) {
        int minIndex = i;   //先把i指向的位置的数设置为最小下标
        for(int j = i + 1; j < arr.length; j++) {//找出这一轮最小值对应的下标
            if(arr[j] < arr[minIndex]) {//若存在,值比最小下标小,则更新最小下标
                minIndex = j;
            }
        }
        swap(arr,i,minIndex);//使得这一轮的最小值归位
    }
}

3.插入排序

public static void insertSort(int[] arr) {
    if(arr == null || arr.length < 2) {
        return;
    }
    for(int i = 1; i < arr.length; i++) {//将外层循环的数插入到前面有序的数组中
        //对前面的数组进行排序：插入的数 从后往前依次比较, 插入的数小就一直往前交换
        for(int j = i - 1; j >=0 && arr[j] > arr[j + 1];j--) {
            swap(arr,j,j + 1);
        }
    }
}

4.希尔排序

public static void shellSort(int[] arr) {
    if(arr == null || arr.length < 2) {
        return;
    }
    int h = 3;//步长定为3
    while(h >= 1) {
        for(int i = h; i < arr.length; i++) {
            for(int j = i - h; j >= 0 && arr[j] > arr[j + h]; j -= h) {
                swap(arr,j,j+h);
            }
        }
        h = h/3;
    }
}

5.归并排序

public static void mergeSort(int[]arr) {
    if(arr == null || arr.length < 2) {
        return;
    }
    mergeSort(arr,0,arr.length - 1);
}
public static void mergeSort(int[] arr,int low, int high) {
    if(low == high) {//递归的终点
        return;
    }
    int mid = low + (high - low)/2;
    mergeSort(arr, low, mid);//递归排序左半部分
    mergeSort(arr,mid + 1, high);//递归排序右半部分
    merge(arr,low,mid,high);  //合并
}
public static void merge(int[] arr,int low, int mid, int high) {
    //生成一个辅助数组,大小和原数组相同
    int[] help = new int[high - low + 1];
    int less = low;//less指向左边数组第一个数
    int more = mid + 1;//more指向右边数组第一个数
    int i = 0; //辅助数组help的索引
    while(less <= mid && more <= high) {
        if(arr[less] <= arr[more]){  //数组两遍哪边的数小就填进辅助数组
            help[i++] = arr[less++];
        }else {
            help[i++] = arr[more++];
        }
    }
    //处理剩余部分
    //右边数组耗尽,把左边数组拷贝到辅助数组
    while(less <= mid) {
        help[i++] = arr[less++];
    }
    //左边数组耗尽,把右边数组拷贝到辅助数组
    while(more <= high) {
        help[i++] = arr[more++];
    }
    //把help数组拷贝到原数组中去
    for(i = 0; i < help.length; i++) {
        arr[low + i] = help[i];
    }
}

6.快速排序

public static void quickSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    quickSort(arr, 0, arr.length - 1);
}

public static void quickSort(int[] arr, int L, int r) {
    if (L < r) {
        // 产生low-high上的随机数, 把这个索引的看做目标数换到数组的最后
        // swap(arr,low + (int)(Math.random()*(high - low + 1)),high);
        int[] p = patition(arr, L, r);// 小于目标数的放左边，大于放右边，等于放中间
        quickSort(arr, L, p[0] - 1);// 递归排序小于区域
        quickSort(arr, p[1] + 1, r);// 递归排序大于区域
    }
}

public static int[] patition(int[] arr, int L, int r) {
    int less = L - 1; // less指向数组的前一位置 ,low~less为小于区域
    int more = r;// more指向最后一个元素,把high元素作为目标数，more - 1~high为大于区域
    while (L < more) { // low作为当前数,直到跟大于区域相等 循环结束
        if (arr[L] > arr[r]) {
            // 当前数比目标数大,跟大于区域的前一个数交换，大于区域数+1,当前数不移动
            swap(arr, --more, L);
        } else if (arr[L] < arr[r]) {
            // 当前数比目标数小,跟小于区域的下一个数交换,小于区域的数+1,当前数向后移动
            swap(arr, ++less, L++);
        } else {
            // 当前数等于目标数,继续移动
            L++;
        }
    }
    swap(arr, more, r); // 把目标数归到等于区域
    return new int[] { less + 1, more }; // 返回等于区域的左下标和右下标
}

7.堆排序

public static void heapSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    //构造堆
    //方法一：可以直接从数组头开始向堆中添加元素
    /*		for (int i = 0; i < arr.length; i++) {
			heapInsert(arr, i);
		}*/
    int size = arr.length;
    //方法二：直接把数组看做堆  然后从最后一个父节点开始调整
    for(int i = (size - 1)/2; i >= 0; i--) {
        heapify(arr,i,size);
    }

    //排序:把堆顶的值和最后一个元素进行交换,并且当前堆长度减少1,然后进行调整使得成为
    while (size > 0) {
        swap(arr, 0, --size);
        heapify(arr, 0, size);
    }
}

//向堆中插入元素    /上浮
public static void heapInsert(int[] arr, int index) {
    //		while (arr[index] > arr[(index - 1) / 2]) {
    //			swap(arr, index, (index - 1) / 2);
    //			index = (index - 1) / 2;
    //		}

}

//堆中的某个元素变化,调整堆结构  / 下沉
public static void heapify(int[] arr, int index, int size) {
    while (index * 2 + 1 < size) {
        int left = index * 2 + 1;
        if(left + 1 < size && arr[left + 1] > arr[left]) {
            left++;
        }
        if(arr[left] <= arr[index]) {
            break;
        }
        swap(arr,index,left);
        index = left;
    }
}

8.桶排序

public static void bucketSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    int max = Integer.MIN_VALUE;
    // 遍历找到数组中的最大值
    for (int i = 0; i < arr.length; i++) {
        max = Math.max(max, arr[i]);
    }
    // 创建一个max+1大小的数组作为桶
    int[] bucket = new int[max + 1];
    // 遍历需要排序的数组,元素的值等于多少就填进那个桶中
    for (int i = 0; i < arr.length; i++) {
        bucket[arr[i]]++;
    }
    // 取出桶中的元素恢复到原数组中
    int j = 0;// arr数组的索引
    for (int i = 0; i < bucket.length; i++) {
        while (bucket[i]-- > 0) {
            arr[j++] = i;
        }
    }
}

二、排序算法复杂度

三、对数器的使用

为了检测算法是否正确,自己的用例可能具有随机性，使用比较器来实现随机。另外在OJ中也可以自己控制随机数的范围。

/**
 * 设置对数器,用来检验结果正确性
 */

 // 1.先有一个绝对正确的方法, 一般是一个复杂度不高但是正确的方法
public static void comparator(int[] arr) {
    Arrays.sort(arr);
}

// 2.实现一个随机样本产生器
/**
 * @param maxSize    随机数组的最大长度,  例如传入10,产生[0,11)的随机数,对于int来说就是1-10
 * @param maxValue    随机数组中元素的随机值的最大值
 * @return            返回一个随机长度  并且元素也是随机的一个数组
 */
public static int[] generateRandomArray(int maxSize, int maxValue) {
    int arr[] = new int[(int) ((maxSize + 1) * Math.random())];
    for (int i = 0; i < arr.length; i++) {
        arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) ((maxValue + 1) * Math.random());
    }
    return arr;
}
//3.实现一个比对方法
public static boolean isEqual(int arr1[],int arr2[]) {
    if(arr1 == null && arr2 != null || arr1 != null && arr2 ==null) {
        return false;
    }
    if(arr1 == null && arr2 == null) {
        return true;
    }
    if(arr1.length != arr2.length) {
        return false;
    }
    for(int i = 0; i < arr1.length; i++) {
        if(arr1[i] != arr2[i]) {
            return false;
        }
    }
    return true;
}
//比较很多次两个方法产生的结果 查看是否相同相同
public static void main(String[] args) {
    int testTime = 10000; //测试次数
    int maxSize = 30;//数组的最大尺寸
    int maxValue = 100;//数组中元素的最大值
    boolean succeed = true;
    for (int i = 0; i < testTime; i++) {
        int arr1[] = generateRandomArray(maxSize, maxValue);//产生随机数组
        int arr2[] = arrayCopy(arr1);//拷贝数组,让这两个数组结构完全相同
        bubbleSort(arr1);  //需要测试的方法
        comparator(arr2);  //绝对正确的方法
        if(!isEqual(arr1, arr2)) {
            succeed = false;
            break;    //判断出不相同就调出循环
        }
    }
    System.out.println(succeed ? "Succeed!" : "Error!");

    int [] arr = generateRandomArray(maxSize, maxValue);
    System.out.println(Arrays.toString(arr));
    bubbleSort(arr);
    System.out.println(Arrays.toString(arr));
}    
//拷贝数组
public static int[] arrayCopy(int[] arr) {
    if(arr == null) {
        return null;
    }
    int[] res = new int[arr.length];
    for (int i = 0; i < arr.length; i++) {
        res[i] = arr[i];
    }
    return res;
}

四、比较器的使用

public class Comparator {
	//实现Comparator接口，并覆盖compare方法
	public static class IdAscendingComparator implements java.util.Comparator<Student>{

		@Override
		public int compare(Student o1, Student o2) {
			if(o1.id < o2.id) {  //o1小返回负数
				return -1;
			}else if(o1.id > o2.id){//o1大返回正数
				return 1;
			}else {
				return 0;//相等返回0
			}
			//return o1.id - o2.id;  //简写
		}
	}
	public static void main(String[] args) {
		Student student1 = new Student("A", 1, 23);
		Student student2 = new Student("B", 2, 21);
		Student student3 = new Student("C", 3, 22);
		Student[] students = new Student[] { student3, student2, student1 };
		System.out.println(Arrays.toString(students));
		Arrays.sort(students, new IdAscendingComparator());
		System.out.println(Arrays.toString(students));
	}
	public static class Student {
		public String name;
		public int id;
		public int age;
		public Student(String name, int id, int age) {
			this.name = name;
			this.id = id;
			this.age = age;
		}
		@Override
		public String toString() {
			return "Student [name=" + name + ", id=" + id + ", age=" + age + "]";
		}
	}
}