排序算法大致分为内部排序和外部排序两种
内部排序：待排序的记录全部放到内存中进行排序，时间复杂度也就等于比较的次数
外部排序：数据量很大，内存无法容纳，需要对外存进行访问再排序，把若干段数据一次读入内存使用内部排序的方法进行排序后写入外存，再将这若干个已经排序的数据进行归并，时间复杂度等于IO(访问外存)的次数
交换排序。属于比较简单直观的排序算法，以升序为例（从小到大），每次比较相邻的两个元素，如果左侧元素比右侧的大，则交换两个元素的位置，每次把循环中最大的元素放在循环的最后，像冒泡一样从小到最大。
总共需要比较次数(n为数组元素个数 n >= 1)：
[O(n)=(n-1)+(n-2)+cdots+1=frac{(n-1)*n}{2}\ 取最高次幂O(n)=n^2 ]
public int[] bubbleSort(int[] arr) {
// 外层循环，数组长度为 n，循环次数为 n-1
for (int i = 0; i < arr.length - 1; i++) {
// 内层循环，循环次数为 n-1-i，找到一个最大值放在，arr[n-1-i]的位置
for (int j = 0; j < arr.length - 1 - i; j++) {
// 比较相邻的两个值，把相对大的值放在数组下标大的地方
if (arr[j] > arr[j + 1]) {
// swap交换
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return arr;
}
如图，即使第二次循环已经排好序，但是程序不晓得，仍会继续循环进行排序，最后一次，只有两个元素进行排序比较，直接排序完成，排序次数 n-1。
交换排序。选择一个基准值，将数组划分两个区域，左侧的值全部比右侧的值小，然后分别对两个区域继续进行区域的划分与排序，直到排序完成。
对区域划分取特殊值，假设n为2的幂，每次都将n个数平均划分，所以第一次对一整个区域进行循环n次划分2个区域，第二次对两个区域分别进行循环(frac{n}{2})次，共n次，划分4个区域，第三次对4个区域分别进行循环(frac{n}{4})次，共计n次，以此类推，最后一次为第log2n次，划分的每个区域仅有一个元素。即：
[O(n)=n*log_2n ]
private static int[] quickSort(int[] arr, int left, int right) {
if (left < right) {
int partitionIndex = partition(arr, left, right);
// 左侧右侧区间再分别进行排序
quickSort(arr, left, partitionIndex - 1);
quickSort(arr, partitionIndex + 1, right);
}
return arr;
}
// 以基准值将数组arr的left~right区间进行分区，保证返回的下标左侧元素比基准值小，右侧比基准值大
private static int partition(int[] arr, int left, int right) {
// 设定基准值为最左侧元素，本身不参与循环中的交换，仅在最后放到index的位置
int pivot = left;
// 该index用于标记一个下标，代表当前已经遍历的元素中，index位置的元素是最后一个比基准值小的元素
// arr[index]本身以及数组左侧元素都小于基准值
int index = left;
// 遍历left+1~right区间（因为基准值自身不需要进行比较交换）
for (int i = left+1; i <= right; i++) {
if (arr[i] < arr[pivot]) {
// 保证从当前遍历到的最后一个比基准值小的元素的下一个元素开始交换，所以先++再交换
index++;
swap(arr, i, index);
}
}
// 此时index为分界点，arr[index]<arr[index+1]
// 其他元素交换完毕之后arr[index]的值应该为基准值，所以进行元素位置交换
swap(arr, pivot, index);
// 此时arr[index]两侧元素左小右大
return index;
}
// 元素交换
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
插入排序。每一次把一个待排序的记录，按照值的大小，插入到有序数组的合适位置。
相当于把a[n]分割，先排序数组 a[0] ~ a[1]，再 a[0] ~ a[2]，直到 a[0] ~ a[n] 全部排序完成。
认为第一元素已经排好序，从第二个元素开始向前比较，计算需要比较的次数：
[O(n) = 1+2+3+cdots+n-1= frac{(n-1)*n}{2}\ 即O(n) = n^2 ]
public static int[] insertionSort(int[] arr){
// 从第二个元素开始到最后一个元素
for (int i = 1; i < arr.length; i++) {
// 向前遍历
for( int j = i ; j > 0 ; j -- ){
if( arr[j] < arr[j-1] ){
swap( arr, j , j-1 );
}
else{
break;
}
}
}
return arr;
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
插入排序。因为设计该算法的人叫Shell，所以叫希尔排序，又称缩小增量排序。思路上是将待排序序列分割成若干个子序列进行直接插入排序，并逐渐缩减少子序列个数，直到针对整体进行一次排序。
希尔排序的时间复杂度和增量的选择有关，证明的话我是不会，最坏时间复杂度是(O(n^2))，当n在某个范围内时，可以达到(O(n^{1.3}))
/**
该代码与实际算法步骤有区别：
算法步骤是说针对每个子序列进行直接插入排序，实际上对每个子序列的直插排序是交替进行的
**/
public static void shellSort(int[] arr) {
int length = arr.length;
// 记录需要进行直接插入排序的值
int temp;
// 增量step从length/2递减到1进行循环
for (int step = length / 2; step >= 1; step /= 2) {
// 进行直插排序，默认第一个元素已经排序完成，从step下标的元素开始向前进行直插
for (int i = step; i < length; i++) {
// 需要对arr[i]进行直接插入排序，记录该值
temp = arr[i];
// j来记录temp最后需要插入的位置
int j = i;
while (j -step >= 0 && arr[j-step] > temp) {
arr[j] = arr[j-step];
j -= step;
}
arr[j] = temp;
}
}
}
// 使用直接插入版本的代码：
private static void shellSort2(int[] arr) {
int len = arr.length;
for (int step = len / 2; step > 0; step = step / 2) {
// 直接插入排序的代码，只不过向前遍历时遍历的数组为i,i-step,i-step-step...
for (int i = step; i < arr.length; i++) {
for (int j = i; j-step >= 0; j -= step) {
if (arr[j] < arr[j - step]) {
swap(arr, j, j - step);
}
}
}
}
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
选择排序。从未排序序列中查找一个最小值，然后将该值放到已排序序列的末尾位置，循环下去，直到最后一个元素。
循环次数为n-1，n-2，n-3，(cdots)，1
[O(n) = (n-1)+(n-2)+cdots+1\ O(n) = frac{1}{2}(n^2-n)\ O(n) = n^2 ]
public static int[] selectionSort(int[] arr){
// 外层循环经过 n-1 轮比较
for (int i = 0; i < arr.length - 1; i++) {
// min用来记录每次比较过程中最小值的下标
int min = i;
// 0~i已经排序完成，从i向后比较查找后面序列的最小值
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[min]) {
// 记录最小值元下标
min = j;
}
}
// 将找到的最小值和i位置所在的值进行交换
if (i != min) {
swap(arr, i ,min);
}
}
return arr;
}
选择排序。将待排序列构造诚大根堆，根节点则为序列中最大元素，将该节点与最后一个值交换，把剩余的节点重新构建大根堆，继续进行交换，直到待排序列只剩下一个值。
大根堆（大顶堆）：父节点一定大于两个子节点的值，即：arr[i] > arr[2i+1] && arr[i] > arr[2i+2]
将大根堆映射到数组中示例：
设元素个数为 n，建堆的高度 (k=log_2(n+1))，
第 i 层的非叶子节点的最大操作（交换）次数为 k-i
第 i 层的节点个数为 (2^{i-1})
所以第 i 层总共需要操作 ((k-i)(2^{i-1})) 次，总共需要操作的次数为
[S = (k-1)*2^0 + (k-2)*2^{1}+(k-3)*2^2+cdots+(k-(k-1))*2^{k-1-1} ]
用 2S - S计算 S 的值:
[S = 2^1+2^2+cdots+2^{k-1}-(k-1)\ S = 2^k-k-1 ]
将 (k=log_2{(n+1)}Approx log_2n) 代入得
[O(n) = n - log_2n-1 \取最高项O(n) = n ]
则初始化大根堆的时间复杂度 O(n) = n
2.重新调整堆
根节点和待排序数组的最后一个元素 a[i] 交换之后，需要重新调整堆，最大调整次数 = a[i] 所在堆的层数 = (log_2i)，总共需要调整的次数 = ((n-1)(log_2n)) ，所以调整堆的时间复杂度为
[O(n) = nlog_2n ]
总的时间复杂度 (O(n) = n + nlog_2n = nlog_2n)
public static int[] HeapSort(int[] arr) {
int len = arr.length;
// 对所有元素建立大根堆
buildMaxHeap(arr, len);
// 从数组尾开始进行循环，每次找到待排序序列的最大值
for (int i = arr.length - 1; i > 0; i--) {
// 此时arr[0]为最大值，交换根节点arr[0]和最后一个节点 i
swap(arr, 0, i);
len--;
// 剩余元素重新建堆
heapify(arr, 0, len);
}
return arr;
}
private static void buildMaxHeap(int[] arr, int len) {
for (int i = len / 2; i >= 0; i--) {
heapify(arr, i, len);
}
}
/**
* @param arr 排序数组
* @param parent 父节点下标
* @param len 待排序数组 length
*/
private static void heapify(int[] arr, int parent, int len) {
// 计算父节点的两个子节点下标
int left = 2 * parent + 1;
int right = 2 * parent + 2;
// largest为父节点和子节点最大值的下标
int largest = parent;
// 比较左右子节点和父节点的大小
if (left < len && arr[left] > arr[largest]) {
largest = left;
}
if (right < len && arr[right] > arr[largest]) {
largest = right;
}
// 如果当前的最大值不是当前父节点，需要进行元素交换，
// 交换之后的子节点作为父节点时不一定是大根堆，需要重新建堆
if (largest != parent) {
swap(arr, parent, largest);
heapify(arr, largest, len);
}
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
初始化大根堆：
循环取堆顶元素排序：建议自己画二叉树更明晰
完整动图：
将两个及以上的有序表合并成一个有序表。以下为两路合并排序。
采用分治法，把无序数组两两分割，分割数次，然后自下至上将两个子序列进行排序，然后合并成一个有序数组，逐渐向上进行两两合并，直到合并成一个有序数组。
时间复杂度 = 两个数组归并排序的时间复杂度 + 重建大根堆的时间复杂度
$f(n) = 2f(frac{n}{2})+ n $
(n = frac{n}{2}) : : (f(frac{n}{2}) = 2f(frac{n}{4}) + frac{n}{4})
(n=frac{n}{4}) : : (f(frac{n}{4})=2f(frac{n}{8}) + frac{n}{8})
(cdots)
(n=frac{n}{2^{m-1}}) : : (f(frac{n}{2^{m-1}}) = 2f(frac{n}{2^m}) + frac{n}{2^{m-1}})
即：(f(n) = 2f(frac{n}{2}) + n)
(=2[2f(frac{n}{4} + frac{n}{4}) + n]) = $ 22f(frac{n}{22}) + 2n$
(=2^2[f(2f(frac{n}{8}) + frac{n}{4})] + 2n) = (2^3f(frac{n}{2^3}) + 3n)
(cdots)
(=2^mf(frac{n}{2^m}) + mn)
当数组被分割成仅剩一个元素时，此时分割为(2^mf(1)+mn) 即： (frac{n}{2^m} = 1)
则：(m = log_2n)
代入得(f(n) = 2^{log_2n}f(1) + n * log_2n = n + nlog_2n)
所以归并排序的时间复杂度为：
[O(n) = nlog_2n ]
public static int[] MergeSort(int[] arr) {
// 数组中仅有一个元素==已排序
if (arr.length < 2) {
return arr;
}
// 分割数组的下标
int middle = arr.length / 2;
// 将数组分割成arr[0] ~ arr[middle-1] 和 arr[middle] ~ arr[length-1] 两部分
int[] left = Arrays.copyOfRange(arr, 0, middle);
int[] right = Arrays.copyOfRange(arr, middle, arr.length);
/**
* 可以拆分为
* int[] arr1 = MergeSort(left);
* int[] arr2 = MergeSort(right);
* 对两个分割后的数组分别再进行归并排序
* return merge(arr1, arr2);
*/
return merge2(MergeSort(left), MergeSort(right));
}
/**
* 将两个数组进行合并方法 1
*/
protected static int[] merge1(int[] left, int[] right) {
// 合并后的数组
int[] result = new int[left.length + right.length];
// i 进行计数，直到等于left或者right数组的长度
int i = 0;
// 循环对left和right数组的首个元素进行比较，把小的放入result数组
// 并重新给left或right数组赋值
while (left.length > 0 && right.length > 0) {
if (left[0] <= right[0]) {
result[i] = left[0];
left = Arrays.copyOfRange(left, 1, left.length);
} else {
result[i] = right[0];
right = Arrays.copyOfRange(right, 1, right.length);
}
i++;
}
// 此时left或right数组有一个已经遍历完毕，直接把剩下的元素全部放入result数组
while (left.length > 0) {
result[i] = left[0];
i++;
left = Arrays.copyOfRange(left, 1, left.length);
}
while (right.length > 0) {
result[i] = right[0];
i++;
right = Arrays.copyOfRange(right, 1, right.length);
}
return result;
}
/**
* 将两个数组进行合并方法 2
* 个人还是倾向于这个直观的
*/
private static int[] merge2(int[] left, int[] right) {
// 合并后的结果
int[] result = new int[left.length + right.length];
// i,j分别用于遍历left，right数组
int i = 0;
int j = 0;
// count用于放入result数组时的下标计数
int count = 0;
// 循环对left和right数组元素进行比较，并把小的赋值给result[count]
// 直到遍历完left或者right数组
while (i < left.length && j < right.length) {
if (left[i] < right[j]) {
result[count] = left[i];
i++;
} else {
result[count] = right[j];
j++;
}
count++;
}
// 此时left或right数组有一个已经遍历完毕，直接把剩下的元素全部放入result数组
while (i < left.length) {
result[count] = left[i];
i++;
count++;
}
while (j < right.length) {
result[count] = right[j];
j++;
count++;
}
return result;
}
注：两个图不是同一个算法过程
取得最大整数的位数，从个位开始进行比较放入新的数组，再收集起来，此时数组按照个位有序排列，再进位进行比较收集，以此类推，直到最高位比较完成，此时数组全部有序。
设n个数的最大值是k位数，需要的桶（收集元素的数组）为r个，进行一次遍历元素收集的时间复杂度为O(n+r)，总的时间复杂度就是O(k(n+r))，一般来说，n >> r 且 n >> k，所以可以认为基数排序的时间复杂度为O(n)，也可以认为事件复杂度为O(kn)。
private static int[] RadixSort(int[] arr, int maxDigit) {
int mod = 10;
int dev = 1;
for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
// 使用二维数组作为桶存放数据
// 考虑负数的情况，其中 [0-9]对应负数，[10-19]对应正数 (bucket + 10)
int[][] counter = new int[mod * 2][0];
for (int j = 0; j < arr.length; j++) {
int bucket = ((arr[j] % mod) / dev) + mod;
counter[bucket] = arrayAppend(counter[bucket], arr[j]);
}
// 收集数组中的数据
int pos = 0;
for (int[] bucket : counter) {
for (int value : bucket) {
arr[pos++] = value;
}
}
}
return arr;
}
// 自动扩容，并保存数据
private static int[] arrayAppend(int[] arr, int value) {
arr = Arrays.copyOf(arr, arr.length + 1);
arr[arr.length - 1] = value;
return arr;
}
// 获取最高位数
private static int getMaxDigit(int[] arr) {
int maxValue = getMaxValue(arr);
return getNumLength(maxValue);
}
// 获取最大值
private static int getMaxValue(int[] arr) {
int maxValue = arr[0];
for (int value : arr) {
if (maxValue < value) {
maxValue = value;
}
}
return maxValue;
}
// 获取最大值的长度
protected static int getNumLength(long num) {
if (num == 0) {
return 1;
}
int length = 0;
for (long temp = num; temp != 0; temp /= 10) {
length++;
}
return length;
}
小伙伴们有兴趣想了解内容和更多相关学习资料的请点赞收藏+评论转发+关注我，后面会有很多干货。
京公网安备 11010802035086号