对一个n位数组进行正排序，每一轮将最小的数放到第一个，第一轮放到第一个位置，第二轮放到第二个位置，一共有n-1轮。每一轮是前一个数和后一个数比较，如果小，那数组所在的索引就是最小数的索引，比较n-i-1次，最后再交换位置
public static void selectionSort(int[] arr){
if (arr.length<2){
return;
}
for(int i = 0; i < arr.length-1; i++){
int minindex = i;
for(int j = i+1; j
时间复杂度O（N2） 空间复杂度O(1)
2、冒泡排序
对一个n位数组正排序，每一轮左边的数和右边的数比较，大的放右边，这样一轮下来，最右边的数就是最大的数，再下一轮，比较第0位置和n-1位置的数，这一轮最大的数放在n-1的位置上，直到最后一轮，也就是第一个数和第二个数比较，一共有n-1轮
public static void bubblesort(int[] arr){
if (arr.length<2){
return;
}
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 i,int j){
arr[i] = arr[i]^arr[j];
arr[j] = arr[i]^arr[j];
arr[i] = arr[i]^arr[j];
}
时间复杂度O(N2) 空间复杂度O(1)
异或运算 相同为0，不同为1
上述swap函数使用前提是 交换的两个变量在内存中不是同一位置，否则将会异或成0
3、插入排序
对一个n位数组正排序，让0~0位置有序，0~1位置有序，0~2位置有序，直到0~n-1位置上数有序，为了让它们内部有序，从第j位置往前看，如果前一位比后一位大，就要进行交换。
public static void insertSort(int[] arr){
if (arr.length<2){
return;
}
for(int i=1;i=0 && arr[j]>arr[j+1];j--){
swap(arr,j,j+1);
}
}
}
最坏时间复杂度O(N2),最好时间复杂度O(N)
4、归并排序
对一个n位数组正排序，从数组中间进行二分，左右数组排好序，然后将左右数组进行归并，创建一个辅助数组进行填充；规则如下：如果左边的数组的值比右边的数组小，则把这个数放到辅助数组中，左边数组指针右移一位；如果左边的比右边的大，右边指针右移一位；直到一方遍历越界，将剩下没有遍历完全的数组放入辅助数组中去。
public static void mergeSort(int[] arr){
if (arr.length<2){
return;
}
process(arr,0,arr.length-1);
}
public static void process(int[]arr,int left,int right){
if (left==right){
return;
}
int mid = left + ((right-left)/2);
process(arr,left,mid);
process(arr,mid+1,right);
merge(arr,left,mid,right);
}
public static void merge(int[]arr,int left,int mid, int right){
int i = 0;
int[] help = new int[right-left+1];
int p1 = left;
int p2 = mid+1;
while (p1<=mid && p2<=right){
help[i++] = arr[p1]<=arr[p2]?arr[p1++]:arr[p2++];
}
while (p1<=mid){
help[i++] = arr[p1++];
}
while (p2<=right){
help[i++] = arr[p2++];
}
for (int j = 0; j < help.length; j++) {
arr[left+j] = help[j];
}
}
时间复杂度O(NlogN)
5、对数器
写一个程序来判断我们写好的排序算法是否是正确的
我们写了一个计数器，可以生成一个随机数组，值范围[0-maxValue]，数组长度也是随机的，testTime是测试次数。看最后两个排序结果是否相等。
public static int[] generateRandom(int maxValue,int maxSize){
int [] arr = new int[(int)(Math.random()*(maxSize+1))];
for (int i = 0; i < arr.length; i++) {
arr[i] = Math.abs((int)(Math.random()*(maxValue+1))-(int)(Math.random()*(maxValue+1)));
}
return arr;
}
public static int[] copyArray(int[] arr){
if (arr==null)
return null;
int[] arr2 = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
arr2[i]=arr[i];
}
return arr2;
}
public static boolean isEqual(int[]arr1,int[]arr2){
boolean flag = true;
for (int i = 0; i < arr1.length; i++) {
if (arr1[i]!=arr2[i])
flag=false;
}
return flag;
}
public static void main(String[] args) {
int maxValue = 100;
int maxSize = 10;
int testTime = 50000;
boolean flag = true;
for (int i = 0; i < testTime; i++) {
int[] arr1 = generateRandom(maxValue,maxSize);
int[] arr2 = copyArray(arr1);
insertSort(arr1);
bubbleSort(arr2);
if (!isEqual(arr1,arr2)){
flag = false;
break;
}
}
System.out.println(flag);
}
6、比较冒泡和插入耗费的时间
public static void main(String[] args) {
int maxValue = 100;
int maxSize = 100000;
int[] arr1 = generateRandom(maxValue, maxSize);
int length = arr1.length;
int[] arr2 = copyArray(arr1);
long start_time = System.currentTimeMillis();
bubbleSort(arr1);
long endtime = System.currentTimeMillis();
long err1 = endtime - start_time;
long start_time2 = System.currentTimeMillis();
mergeSort(arr2);
long endtime2 = System.currentTimeMillis();
long err2 = endtime2 - start_time2;
System.out.println("数组长度" + length);
System.out.println("冒泡排序用时:" + err1 + "ms");
System.out.println("归并排序用时:" + err2 + "ms");
}
差别有点大~，这就是O(NlogN)和O(N2)的差距了，归并算法真强！
7、快速排序
快速排序的思想就是，找到一个基准点，定义左右两个指针，如果左指针比basic小等于，右移动，大于停止移动；右指针大于等于basic，左移动，小于basic停止移动，左右两个指针指向的值位置交换，直到左右两个指针指向同一位置。这样的话就做到了，左边都是小于basic的数，右边都是大于basic的数。将基准数放到中间位置，对左右两侧的数进行quicksort递归。
public static void quickSort(int[] arr) {
if (arr.length < 2 || arr == null) {
return;
}
quickSort(arr,0,arr.length-1);
}
public static void quickSort(int[] arr, int left, int right) {
if (left < right) {
swap(arr, left + (int) (Math.random() * (right - left + 1)), right);
int[] temp = partition(arr, left, right);
quickSort(arr, left, temp[0] - 1);
quickSort(arr, temp[1] + 1, right);
}
}
public static int[] partition(int[] arr,int left,int right){
int more = right; // >区左边界
int less =left-1;
while (leftarr[right]){
swap(arr,--more,left);
}
else {
left++;
}
}
swap(arr,more,right);
return new int[]{less+1,more};
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
int[] arr = {2, 3, 1, 3, 2, 5};
quickSort(arr);
for (int j : arr) {
System.out.println(j);
}
}
时间复杂度nlogn
8、堆排序
首先把一个数组从左往右依次排列成堆结构，确保父节点比子节点的数都要大，也就是大根堆。然后把第一个数和最后一个数进行交换，堆的数量减一，那最大的数就在最后，再将剩下的变成大根堆，周而复始。
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// heapify:某个数在index的位置，能否往下移动
public static void heapify(int[] arr, int index, int heapSize) {
int left = index * 2 + 1; // 左孩子下标
while (left < heapSize) { //下方还有左孩子
int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
largest = arr[largest] > arr[index] ? largest : index;
if (largest == index) {
break;
}
swap(arr, largest, index);
index = largest;
left = 2 * index + 1;
}
}
//某个数现在在index位置，能否继续向上移动
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 heapSort(int[]arr) {
if (arr.length < 2) {
return;
}
for (int i = 0; i < arr.length; i++) {
heapInsert(arr, i); // 构造一个大根堆
}
int heapSize = arr.length;
swap(arr,0,--heapSize); // 最大的数放在最后的位置上了
while (heapSize>0){
heapify(arr,0,heapSize); //将剩下的数变成大根堆
swap(arr,0,--heapSize);
}
}
时间复杂度O(NlogN)
拓展问题：
已知一个几乎有序的数组，几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离可以不超过K，并且k相对于数组来说比较小。请选择一个合适的排序算法针对这个数据进行排序。
思考方式：
将前K个数构成一个小根堆，那么最顶层节点一定是这个数组中最小的数，拿出放到数组中；接下来对于第i个数到第k+i-1个数依次进行小根堆的构建，依次取出第一个数放到数组中；
public static void minHeapSort(int[] arr,int k) {
PriorityQueueheap = new PriorityQueue();
int index = 0;
for (; index < Math.min(k,arr.length) ; index++) {
heap.add(arr[index]);
}
int i = 0;
for (; index < arr.length; index++,i++) {
arr[i] = heap.poll();
heap.add(arr[index]);
}
while (!heap.isEmpty()){
arr[i++] = heap.poll();
}
}
public static void main(String[] args) {
int[] arr = {1, 3, 2, 5, 6, 8, 7};
minHeapSort(arr, 2);
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
9、比较器
在Java中经常会涉及到对象数组的排序问题，那么就涉及到对象之间的比较问题。
第一种方法比较便于理解，复写equals()方法一般用于自己实现的对象数组排序，而对于在应用Java内置的排序算法时，使用后两种方式都是可以实现的。
先来看一下第二种方式，这种方式就是让自己编写的类继承Comparable接口，并实现接口的compareTo()方法，这种情况下，在使用java.util.Arrays.sort()方法时不用指定具体的比较器，sort()方法会使用对象自己的比较函数对对象进行排序。具体实例代码如下：
public static class Acomp implements Comparator {
// 第一个参数-第二个参数，返回正数，第二个数排前面，也就是小根堆排序
@Override
public int compare(Integer arg0, Integer arg1) {
return arg0 - arg1;
}
}
public static void main(String[] args) {
PriorityQueue heap = new PriorityQueue<>(new Acomp());
heap.add(6);
heap.add(7);
heap.add(3);
heap.add(2);
while (!heap.isEmpty()) {
System.out.println(heap.poll());
}
}
10、桶排序
对于一个数组[111,72,21,1,83,88,55]
桶排序的次数取决于最大值的位数（以十进制为基准），这个数组就是进行三次桶排序。我们创造一个辅助数组bucket作为原数组的辅助空间，再创建一个记数数组，长度为10，将各位数字从右往左遍历，count记录数组中个位数在0-9出现的次数，然后将它们累加。从右往左取出原数组中的数，那个数放到bucke[count[j]-1]t位置上.
public static void radixSort(int[]arr){
if (arr.length<2){
return;
}
radixSort(arr,0,arr.length-1,maxbits(arr));
}
public static int maxbits(int[]arr){
int max = Integer.MIN_VALUE;
for (int i = 0; i < arr.length; i++) {
max=Math.max(max,arr[i]);
}
int res = 0;
while (max!=0){
res++;
max/=10;
}
return res;
}
public static void radixSort(int[] arr, int L, int R, int digit) {
final int radix = 10;
int i = 0, j = 0;
int[] bucket = new int[R - L + 1];
for (int d = 1; d <= digit; d++) {
int[] count = new int[radix];
for (i = L; i <= R; i++) {
j = getDigit(arr[i],d);
count[j]++;
}
for (i = 1; i < radix; i++) {
count[i] = count[i] + count[i-1];
}
for (i = R;i>=L;i--){
j = getDigit(arr[i],d);
bucket[count[j]-1] = arr[i];
count[j]--;
}
for (i=L,j=0;i<=R;i++,j++){
arr[i]=bucket[j];
}
}
}
// 给一个数取出第j位上的数字
public static int getDigit(int x, int d){
return ((x/((int)Math.pow(10,d-1)))%10);
}
public static void main(String[] args) {
int[]arr = {1,3,512,232,12,34,123};
radixSort(arr);
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
时间复杂度：O(N + C)，C=N*(logN-logM)对于待排序序列大小为 N，共分为 M 个桶
