import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 将给定数组排序
* @param arr int整型一维数组 待排序的数组
* @return int整型一维数组
*/
public int[] MySort (int[] arr) {
// write code here
if (arr.length < 2) {
return arr;
}
//return bubbleSort(arr);//冒泡排序
//return fastSort(arr, 0, arr.length - 1);//快速排序
//return insertSort(arr);//插入排序
//return hellSort(arr);//希尔排序
//return selectSort(arr);//选择排序
//return mergeSort(arr, 0, arr.length - 1); //归并排序
return heapSort(arr);//堆排序
//return radixSort(arr);//基数排序
}
//冒泡排序：从头开始遍历，如果当前数比下一个数大，就交换，扫完一遍后再扫一遍，每扫一遍终点-1
public int[] bubbleSort(int[] arr) {
int n = arr.length;
int temp;
boolean isChanged =
false;//如果一次循环中一个位置都没改，那就已经排好了，退出循环即可。
for (int i = 0; i < n - 1; i++) {
isChanged = false;
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
isChanged = true;
}
}
if (!isChanged) {
break;
}
}
return arr;
}
//快速排序：选择数组中任意一个数，将其作为target，定义一头一尾两个指针，
//如果尾指针的值比它小，将尾指针的值赋给头指针，否则尾指针左移
//如果头指针的比他大，将头指针的值赋给尾指针，否则头指针右移
//直到头尾指针重合，将该数的值修改为target
//此时target以左的值都比他小，target以右的值都比他大
//将这两部分再次进行快速排序
//直到传进来的头尾指针本就相等。
public int[] fastSort(int[] arr, int start, int end) {
if (start >= end) {
return arr;
}
int target = arr[start];
int head = start;
int rear = end;
while (head < rear) {
while (arr[rear] > target && head < rear) {
rear--;
}
if (head < rear) {
arr[head] = arr[rear];
head++;
}
while (arr[head] < target && head < rear) {
head++;
}
if (head < rear) {
arr[rear] = arr[head];
rear--;
}
}
arr[head] = target;
fastSort(arr, start, head - 1);
fastSort(arr, head + 1, end);
return arr;
}
//插入排序：从第二个数开始向前遍历，
//如果前面的数比它大，那就交换位置，继续向前遍历
//如果前面的数比它小，说明前面都有序了，那就再从下一个数开始遍历
public int[] insertSort(int[] arr) {
int n = arr.length;
int target;
for (int i = 1; i < n; i++) {
target = arr[i];
int j;
for (j = i - 1; j >= 0; j--) {
if (arr[j] > target) {
arr[j + 1] = arr[j];
} else {
break;
}
}
arr[j + 1] = target;
}
return arr;
}
//希尔排序：希尔排序是插入排序的变种
//因为插入排序如果是个几乎倒序的数组，那么时间复杂度会很高，所以用希尔排序优化
//希尔排序通过数组长度得到步长
//如题目给的数组【5，2，3，1，4】，5/2=2，步长为2
//那么5，3，4为一组，2，1为一组进行插入排序
//再将步长减半，重复操作
//直到步长为0
public int[] hellSort(int[] arr) {
int n = arr.length;
int step = arr.length / 2;
int target;
while (step > 0) {
for (int i = step; i < n; i++) {
int j;
target = arr[i];
for (j = i - step; j >= 0; j -= step) {
if (arr[j] > target) {
arr[j + step] = arr[j];
} else {
break;
}
}
arr[j + step] = target;
}
step /= 2;
}
return arr;
}
//选择排序：选择排序每遍历一次数组，找到里面的最大值放到后面，然后再从头遍历到末尾-1，直到遍历完
//找最小的数放在前面也可以
public int[] selectSort(int[] arr) {
int n = arr.length;
int max;
int index;
for (int i = 0; i < n; i++) {
max = arr[0];
index = 0;
for (int j = 0; j < n - i; j++) {
if (arr[j] > max) {
max = arr[j];
index = j;
}
}
max = arr[n - i - 1];
arr[n - i - 1] = arr[index];
arr[index] = max;
}
return arr;
}
//归并排序：本质是将两个有序数组合并为一个有序数组
//但给的单数组不是有序数组且只有一个
//因此要将连续对半分
//直到变成一系列只含有一个数的数组
//将这些数组两两合并，直到合并回一个数组
public int[] mergeSort(int[] arr, int start, int end) {
if (start == end) {
return arr;
}
int middle = (start + end) / 2;
//将前面一半送入递归
mergeSort(arr, start, middle);
mergeSort(arr, middle + 1, end);
merge(arr, start, middle, end);
return arr;
}
public void merge(int[] arr, int start, int middle, int end) {
if (start == end) {
return;
}
int i = start;
int j = middle + 1;
int index = 0;
int[] temp = new int[end - start + 1];
while (i <= middle && j <= end) {
while (i <= middle && arr[i] < arr[j]) {
temp[index] = arr[i];
index++;
i++;
}
if (i > middle) {
break;
}
while (j <= end && arr[i] >= arr[j]) {
temp[index] = arr[j];
index++;
j++;
}
}
if (i > middle) {
while (index < temp.length) {
temp[index++] = arr[j++];
}
}
if (j > end) {
while (index < temp.length) {
temp[index++] = arr[i++];
}
}
for (int k = start; k <= end; k++) {
arr[k] = temp[k - start];
}
}
//堆排序，将数组转化为大顶堆，从倒数第一个子树开始调整，
//调整的方式为对比根节点与两个子树的值
//若子节点有比根节点大的，就将其中最大的与根节点的值作交换
//这样就能保证每个根节点的值都比其子树大，从而大顶堆的根节点就是最大的数
//然后从最后一个数开始，将其与根节点交换，即将最大值放到最后
//然后调整大顶堆，使根节点替换为次大值。
public int[] heapSort(int[] arr) {
for(int i = (arr.length-2)/2; i >= 0; i--){
adjustHeap(arr,i,arr.length);
}
for(int i = arr.length - 1; i >= 0; i--){
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
adjustHeap(arr,0,i);
}
return arr;
}
public void adjustHeap(int[] arr, int i, int len){
int left = 2*i + 1;
int right = 2*i + 2;
int max = i;
if(left<len && arr[left] > arr[max]){
max = left;
}
if(right<len && arr[right] > arr[max]){
max = right;
}
if(max!=i){
int temp = arr[max];
arr[max] = arr[i];
arr[i] = temp;
adjustHeap(arr,max,len);
}
}
//基数排序：
//将每个数根据其个位放入对应的数组中，再按照0-9的顺序从数组按照先进先出的顺序中取出
//对数据的十位、百位……最高位都如此处理
//准备两组容器
//一组容器是一个二维数组，包含十个一维数组
//另一组容器是一个一维数组，存储0-9数组中的元素个数，方便存取
public int[] radixSort(int[] arr) {
int n = arr.length;
int[][] radix = new int[10][n];
int[] counts = new int[10];
int max = 0;
int cur;
for (int i = 0; i < n; i++) {
cur = String.valueOf(arr[i]).length();
if (cur > max) max = cur;
}
int ys;
for (int i = 0, j = 1; i < max; i++, j *= 10) {
for (int k = 0; k < n; k++) {
ys = arr[k]/j%10;
radix[ys][counts[ys]] = arr[k];
counts[ys]++;
}
//再从基数数组里面倒出来
int index = 0;
for(int k = 0; k < 10; k++){
for(int z = 0; z < counts[k]; z++){
arr[index++] = radix[k][z];
}
counts[k] = 0;
}
}
return arr;
}
}
京公网安备 11010502036488号