今天是：
带着程序的旅程，每一行代码都是你前进的一步，每个错误都是你成长的机会，最终，你将抵达你的目的地。
排序算法
public class Sort {
冒泡排序
每一趟排序将未排序中最大值交换最后，每一趟处理一个最大值，需要进行n-1趟，每一趟需要与n-i次交换.
时间复杂度T(n)=n-1+n-2+...+2+1=n(n-1)/2=O(n²)
public static int[] bubbleSort(int[] unSorted) {
for (int i = 0; i < unSorted.length - 1; i++) {
for (int j = 0; j < unSorted.length - 1 - i; j++) {
if (unSorted[j + 1] < unSorted[j]) {
int temp = unSorted[j];
unSorted[j] = unSorted[j + 1];
unSorted[j + 1] = temp;
}
}
}
return unSorted;
}
选择排序
假设第1个是最小值，从第二个到第n个中选出最小的和当前最小值交换，之后进行相同的操作。总共需要n-1次选择，每次选择需要n-i次判断
时间复杂度T(n)=n-1+n-2+...+2+1=n(n-1)/2=O(n²)
public static int[] selectionSort(int[] arr) {
int minIndex = 0, temp = 0;
for (int i = 0; i < arr.length - 1; i++) {
minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
return arr;
}
插入排序
从第二个开始依此与前面以排好序的数比较，一次比较前面是否有比自己大的数并且往后移动，每次只移动一个，因为当前的数据已尽拿出来了。相当于给后移腾出一个位置。当找到合适的配置，就把当前的值赋值当前位置上。
假如没有比自己大的，相当于什么也没做，位置还是原来的位置
//插入排序,将未排序的插入到已排序的对应的位置中
public static int[] insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int preIndex = i - 1;//已排序最后一个元素索引
int current = arr[i];//当前需要排序的元素
//找出合适的位置
while (preIndex >= 0 && arr[preIndex] > current) {
arr[preIndex + 1] = arr[preIndex];
preIndex--;
}
赋值当前值
arr[preIndex + 1] = current;
}
return arr;
}
希尔排序
分成多个组进行插入排序。最后gap==1是就是单个插入排序，不过此时序列已是基本有序，所要移动的比较少
//希尔排序，按增量分组，增量逐渐减少，知道分为一个组；每个分组按插入排序排序
public static int[] shellSort(int[] arr) {
int len = arr.length;
for (int gap = len / 2; gap > 0; gap /= 2) {
for (int i = gap; i < len; i++) {
//插入排序
int temp = arr[i];
int j;
这里为什么是这样，假设当前gap=3，那么gap=3之后（包括=3）的元素必定和前面三个元素同组中的一个元素
也就是插入排序往前找合适的位置是以gap跳跃的。
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
arr[j] = arr[j - gap];
arr[j] = temp;
}
}
return arr;
}
快速排序
适合分布不均匀，大规模的数据
快排就是先选择一个基准数据，然后把大于它的放在右边，小于它的放在左边。然后在递归分组。这里有两种方式，如下代码
public static int[] quickSort(int arr[], int begin, int end) {
if (begin < end) {
int partitionIndex = partition(arr, begin, end);
quickSort(arr, begin, partitionIndex - 1);
quickSort(arr, partitionIndex + 1, end);
}
return arr;
}
//从头开始设置两个指针 大哥end在前面，小弟i=begin-1跟在大哥屁股后面。
//大哥从第一个元素开始探索。如果大哥发现一个大于基准数据。
//小弟往前走一步，然后把它放在小弟所指的位置。
//即小弟后面跟的都是小雨基准数据。它前面是大于基准的数据，
//还有未探索完的。当大哥探索完以后，把基准数据插到小弟前面，这样和大哥分开了。
private static int partition(int arr[], int begin, int end) {
int pivot = arr[end];
int i = (begin - 1);
for (int j = begin; j < end; j++) {
if (arr[j] <= pivot) {
i++;
int swapTemp = arr[i];
arr[i] = arr[j];
arr[j] = swapTemp;
}
}
int swapTemp = arr[i + 1];
arr[i + 1] = arr[end];
arr[end] = swapTemp;
return i + 1;
}
/*设置两个指针，分别是begin，end，然后右边while找到小于基准的数据就停下，
把它赋值到左边指针所在位置，左边指针往右走，找到大于基准数据就把它赋值给右指针坐在位置
（这里因为基准数据位置不定，因此做的不是交换，而是直接赋值）。
当begin=end是，begin对end所，我后面已经没有比基准大的数据都是小雨基准的数据，
你不用找了。end对begin说，我后面也没有比基准小的数据的了。ok下课，任务完成。有缘再见。*/
private static int partition2(int[] arr, int begin, int end) {
int pivot = arr[begin];
while (begin<end) {
while (begin < end && arr[end] >= pivot) {
end--;
}
arr[begin] = arr[end];
while (begin < end && arr[begin] <= pivot) {
begin++;
}
arr[end] = arr[begin];
}
arr[begin] =pivot;
return begin;
}
归并排序
将两个或两个以上的的序列合并成一个新的有序序列。采用分治法，划分序列，当个序列中只有一个元素时，停止划分，开始合并。
两两合并称为2路归并，多个合并称为多路归并。其思想就是。每个序列设置开始读取指针，按当前指针上数据大小放入新序列中。如果其中一个序列先拉取完了。2路归并下，另一个序列是有序并且大于归并中的序列，直接移动到当前归并序列中。
适合大文件排序，是稳定的排序算法
//归并排序
public static int[] mergeSort(int[] arr, int low, int high) {
int mid = (low + high) / 2;
if (low < high) {
mergeSort(arr, low, mid);
mergeSort(arr, mid + 1, high);
merge(arr, low, mid, high);
}
return arr;
}
private static void merge(int[] arr, int low, int mid, int high) {
int[] temp = new int[high - low + 1];
int i = low;// 左指针
int j = mid + 1;// 右指针
int k = 0;
// 把较小的数先移到新数组中
while (i <= mid && j <= high) {
if (arr[i] < arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
// 把左边剩余的数移入数组
while (i <= mid) {
temp[k++] = arr[i++];
}
// 把右边边剩余的数移入数组
while (j <= high) {
temp[k++] = arr[j++];
}
// 把新数组中的数覆盖nums数组
for (int k2 = 0; k2 < temp.length; k2++) {
arr[k2 + low] = temp[k2];
}
}
桶排序
假设数据均匀分布， 将数据映射到多个桶中，然后对桶中的数据排序，然后按桶的位置依此拿出数据形成已排序数组。主要在于计算桶的数量和映射。下面是简单形式，主要体现桶排序的过程
适合均匀分布的数据，对数据范围以知的
public static void bucketSort(int arr[]){
int min = Arrays.stream(arr).min().getAsInt();
int max = Arrays.stream(arr).max().getAsInt();
int bucketNum= (max-min)/arr.length+1;
List<List<Integer>> buckets = new ArrayList<>(bucketNum);
for (int i = 0; i <bucketNum ; i++) {
buckets.add(new ArrayList<>());
}
Arrays.stream(arr).forEach(num->{
int index = (num-min)/bucketNum;
buckets.get(index).add(num);
});
AtomicInteger i= new AtomicInteger();
buckets.forEach(b->{
if(b.isEmpty()) return;
Collections.sort(b);
b.forEach(num->arr[i.getAndIncrement()]=num);
});
}
堆排序
构建大顶堆或小顶堆，然后把根结点移动到已排序位置，对于剩余未排序的重复之前的堆操作。适合外部排序，如大文件排序
public static int[] heapSort(int[] arr)
{
int n = arr.length;
// 构建堆，从最后一个非叶子结点开始，完全二叉树性质
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// One by one extract an element from heap
for (int i=n-1; i>=0; i--)
{
// Move current root to end
将堆顶即最大值移到数组已排序位置
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
当前堆顶可能已经不满足大顶堆，重新调整
// call max heapify on the reduced heap
heapify(arr, i, 0);
}
return arr;
}
// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
private static void heapify(int arr[], int n, int i)
{
int largest = i; // Initialize largest as root
//做孩子和右孩子，完全二叉树性质
int l = 2*i + 1; // left = 2*i + 1
int r = 2*i + 2; // right = 2*i + 2
// If left child is larger than root
if (l < n && arr[l] > arr[largest])
largest = l;
// If right child is larger than largest so far
if (r < n && arr[r] > arr[largest])
largest = r;
// If largest is not root
if (largest != i)
{
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
}
计数排序
统计源数组每个值出现的次数，按数值从小到大依次放入辅助数组，并切计算距离最小值的位置，然后遍历原数组，从辅助数组中找出当前数据在排序数组中的位置填入。适合量大但是数据范围比较小的数据
static int[] countingSort(int[] arr) {
int max =0;
int min =0;
for (int i = 0; i <arr.length ; i++) {
if(arr[i]<min) min= arr[i];
if(arr[i]>max) max=arr[i];
}
int range = max - min + 1;
int[] count = new int[range];
int[] result = new int[arr.length];
// 统计元素出现次数
for (int num : arr) {
count[num - min]++;
}
// 累加数组 。计算完之后就可以知道原值距离最小值位置
for (int i = 0; i < range-1; i++) {
count[i+1] += count[i];
}
// 构造排序结果，
for (int i = arr.length - 1; i >= 0; i--) {
//把当前值赋值在排序数组中对应的位置
result[count[arr[i] - min] - 1] = arr[i];
//相同数的值-1，因为count中如果一个数有多个，纪录的最后一个的位置
count[arr[i] - min]--;
}
// 将排序结果拷贝回原数组
//System.arraycopy(result, 0, arr, 0, arr.length);
return result;
}
基数排序
对原数组分别进行各位，十位 ... 排序，每趟排序可以使用计数和桶排序。 当最高位排序完成之后，序列以有序
static void radixSort(int arr[]) {
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
for (int exp = 1; max / exp > 0; exp *= 10) {
countingSort(arr, exp);
}
}
static void countingSort(int arr[], int exp) {
int n = arr.length;
int output[] = new int[n];
int count[] = new int[10];
for (int i = 0; i < n; i++) {
count[(arr[i] / exp) % 10]++;
}
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
for (int i = n - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
System.arraycopy(output, 0, arr, 0, n);
}
分享到：
