常见排序代码总结(Java语言实现)

最近继续重温下数据结构中的排序，其实之前在三月份得时候也有复习过了一遍，其实前人已经总结得很不错了，这次重新再过一遍，重新手写一下代码：

以下代码的swap代码都是基于如下代码：
使用位运算，更快更有逼格~

private static 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];
}

冒泡排序：

• 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
• 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
• 针对所有的元素重复以上的步骤，除了最后一个。
• 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

  public static void bubbleSort (int [] array) {
    for (int i = array.length - 1; i > 0; i--) {
        boolean flag = true;
        for (int j = 0; j < i; j++) {
            if (array[j] > array[j+1]) {
                swap(arr,j,j+1);
                flag = false;
            }
        }
        if (flag) break;
    }
  }

选择排序：

• 在序列中找到最小（大）元素，放到序列的起始位置作为已排序序列；
• 再从剩余未排序元素中继续寻找最小（大）元素，放到已排序序列的末尾。

  public void selectSort(int [] arr) {
    for (int i = 0; i < arr.length; i++) {
        int minIndex = i;
        for (int j = i + 1; j < arr.length; j++) {
            minIndex = arr[j] < arr[minIndex] ? j : minIndex;
        }
        swap(arr,i,minIdex);
    }
  }

  插入排序

• 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
• 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

  public static void insertSort(int [] arr) {
    for (int i = 1; i < arr.length; i++) {
        int tmp = arr[i];
        for (int j = i - 1; j >= 0 && tmp < arr[j]; j--) {
            arr[j+1] = arr[j];
        }
        arr[j+1] = tmp;
    }
  }

希尔排序

希尔排序是更高效的插入排序，它把数组分成几块，每一块进行一个插入排序；
而分块的依据在于增量的选择分好块之后，从gap开始到n，每一组和自己组内的元素进行插入排序；
这里以gap为2为例。

public void shellSort(int [] arr) {
    //增量序列,这里为2
    for (gap = arr.length; gap > 0; gap /= 2){
        //从数组第gap个元素开始
        for (int i = gap; i < gap; i++) {
            int tmp = arr[i],j;
            //每个元素与自己组内的数据进行直接插入排序
            for (j = i - gap; j >= 0 && tmp < arr[j]; j-= gap) {
                arr[j+gap] = arr[j];
            }
            arr[j] = tmp;
        }
    }
}

快速排序

原始快速排序：

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

static void quick(int [] arr, int L, int R){
    if (L >= R) return;
    int p = partition(arr,L,R);
    quick(arr,L,p - 1);
    quick(arr,p + 1,R);

}
// 返回pivot，使得左边都小于切分数，右边都大于切分数
static int partition(int [] arr, int L, int R) {
    //获取第一个为切分元素
    int num = arr[L];
    int pivot = L;
    for (int i = L + 1; i <= R; i++) {
        if (arr[i] < num) {
            swap(arr,i,++pivot);
        }
    }
    swap(arr,L,pivot);
    return pivot;

}

这种情况的快速排序有两种弊端，一是每次选第一个为切分元素，如果是最小值或者最大值，这样比较不好，还有就是说上面那种在partition中的时候只有一个指针，如果排序的数组重复元素很多的情况下，还是会使得划分极其的不均匀。

改进版快速排序（推荐）：(注意区分与上面的不同)

1. 写一个切分方法partition
2. 然后每一次切分完成后递归调用quick方法，缩小区间。

   static void quickSort(int [] arr) {
    if (arr.length <= 1) return;
    quick(arr,0,arr.length - 1);
   }
   static void quick(int [] arr,int L, int R) {
    if (L >= R) return;
    // 随机选取
    swap(arr,L,L+(int)(Math.random()*(R - L + 1)));
    int p = partition(arr,L,R);
    quick(arr, L, p - 1);
    quick(arr, p + 1, R);
   }
   static int partition(int [] arr,int L, int R) {
    int num = arr[L];
    //两个节点
    int less = L + 1, more = R;
    while (true) {
        while (less < R && arr[less] < num) less++;
        while (more > L) && arr[more] > num) more--;
        if (less >= more) break;
        swap(arr, less++, more--);
    }
    //最后跟L交换的是more
    swap(arr,L,more);
    return more;
   }

堆排序

堆排序的过程是一个反复调整堆的过程：

• 利用数组建立一个大根堆（父亲比孩子的值大）；
• 把堆顶元素和堆尾元素互换；
• 把堆（无序区）的尺寸缩小1，并下沉；
• 重复步骤，直到堆的大小为1；

private void HeapSort(int [] arr) {
    int N = arr.length - 1;
    for (int i = N / 2; i >= 1; i--) {
        sink(arr,i,N);
    }
    while (N > 1){
        swap(arr,1,N--);
        sink(arr,1,N);
    }

}
//下沉
private void sink(int [] arr,int k,int N) {
    while (2 * k <= N) {
        int j = 2 * k;
        //与两个子节点中最大的节点进行交换
        if (j < N && arr[j] < arr[j+1]) j++;
        if (arr[k] >= arr[j]) {
            break;
        }
        // 下沉
        swap(arr,k,j)

        k = j;    
    }
}

归并排序

归并排序采用分治的思想，这里用递归实现，首先先递归拆分子序列，然后将两个已经有序的子序列合并成一个有序序列，需要准备一个额外的数组(temp)，使其大小为原来数组长度，该空间用来存放合并后的序列。
关键代码是 merge那一部分

private void mergeSort(int [] arr) {
    //创建临时数组
    int temp[] = new int[arr.length];
    sort(arr,0,arr.length - 1,temp);
}
private void sort(int []arr,int l,int r,int [] temp) {
    if (l < r){
        int mid = (l + r) / 2;
        //递归，左边归并排序，使得左子序列有序
        sort(arr,l,mid,temp);
        //右边归并排序，使得右子序列有序
        sort(arr,mid+1,r,temp);
        //将两个有序子数组合并操作
        merge(arr,l,mid,r,temp);
    }
}
//关键代码
private void merge(int []arr,int l,int mid,int r,int [] temp) {
    int i = l;
    int j = mid + 1;
    // 临时变量
    int t = 0;
    while (i <= mid && j<= r) {
        if (arr[i] <= arr[j]) {
            temp[t++] = arr[i++];
        } else {
            temp[t++] = arr[j++];
        }
    }
    //将左边剩余元素填充进temp中
    while (i <= mid) {
        temp[t++] = arr[i++];
    }
    //将右边剩余元素填充进temp中
    while (j <= r) {
        temp[t++] = arr[j++];
    }

    //将temp中的元素全部拷贝到原数组中
    t = 0;
    while (l <= r) {
        arr[l++] = temp[t++];
    }
}

这里七个排序算是比较常见的排序方式了，要好好熟悉，尤其是快排、堆排，平时刷题偶尔也可以用到，比如说快排的partition可以用来求无序数组中的第K大的数字，堆排序用来做优先队列可以用来求最大值最小值等等。
end~