=
class Solution {
public int[] sortArray(int[] nums) {
if (nums == null || nums.length < 2)
return nums;
// insertSort(nums);
// binaryInsertSort(nums);
// shellSort(nums);
// bubbleSort(nums);
// quickSort(nums,0,nums.length-1);
// selectSort(nums);
// heapSort(nums);
// mergeSort(nums,0,nums.length-1,new int[nums.length]);
radixSort(nums);
return nums;
}
//==========>直接插入排序
private void insertSort(int[] nums) {
for (int i = 1; i < nums.length; i++) {
int j = i - 1, temp = nums[i];
while (j >= 0 && nums[j] > temp)
nums[j + 1] = nums[j--];
nums[j + 1] = temp;
}
}
//==========>折半插入排序
private void binaryInsertSort(int[] nums) {
for (int i = 1; i < nums.length; i++) {
int left = 0, right = i - 1, temp = nums[i];
while (left <= right) {
int mid = left + (right - left) / 2;
if (temp >= nums[mid])
left = mid + 1;
else
right = mid - 1;
}
for (int j = i - 1; j >= left; j--)
nums[j + 1] = nums[j];
nums[left] = temp;
}
}
//==========>希尔排序：无序 ——> 有点序 ——> 差点有序 ——> 有序（优化插入排序<因为在倒排会退化>）
private void shellSort(int[] nums) {
int n = nums.length;
for (int d = n / 2; d >= 1; d /= 2) {
for (int i = d; i < n; i++) {
int temp = nums[i], j = i - d;
while (j >= 0 && temp < nums[j]) {
nums[j + d] = nums[j];
j -= d;
}
nums[j + d] = temp;
}
}
}
//==========>冒泡排序
private void bubbleSort(int[] nums) {
int n = nums.length;
for(int i = 0 ; i < n - 1 ; i++){
boolean swapped = false;
for(int j = 1 ; j <= n - 1 - i ; j++){
if(nums[j] < nums[j-1]){
swap(nums,j,j-1);
swapped = true;
}
}
if(!swapped) break;
}
}
//==========>快速排序
private void quickSort(int[] nums,int left,int right){
if(left >= right) return;//<=1个元素已经有序
int mid = partition(nums,left,right);
quickSort(nums,left,mid-1);
quickSort(nums,mid+1,right);
}
private int partition(int[] nums,int left,int right){
int pivotIndex = left + (int)(Math.random() * (right - left + 1));
swap(nums,left,pivotIndex);
int pivot = nums[left], i = left + 1, j = right;
while(true){
while(i <= j && pivot < nums[j]) j--;
while(i <= j && pivot > nums[i]) i++;
if(i >= j) break;
swap(nums,i++,j--);
}
swap(nums,j,left);
return j;
}
//==========>双向选择排序
private void selectSort(int[] nums){
int left = 0, right = nums.length - 1;
while(left < right){
int minIndex = left, maxIndex = left;
for(int i = left+1; i <= right ; i++){
if(nums[i] < nums[minIndex]) minIndex = i;
if(nums[i] > nums[maxIndex]) maxIndex = i;
}
if(minIndex != left) swap(nums,left,minIndex);
if(maxIndex == left) maxIndex = minIndex;
if(maxIndex != right) swap(nums,maxIndex,right);
left++;
right--;
}
}
//==========>堆排序
private void heapSort(int[] nums){
int n = nums.length;
for(int i = (n - 1)/ 2 ; i >= 0 ; i--){
downAdjust(nums,i,n - 1);
}
for(int i = n - 1 ; i > 0 ; i--){
swap(nums,0,i);
downAdjust(nums,0,i-1);
}
}
private void downAdjust(int[] nums,int i,int endIndex){
int child = 2*i+1;
int temp = nums[i];
while(child <= endIndex){
if(child + 1 <= endIndex && nums[child+1] > nums[child]) child++;
if(temp >= nums[child]) break;
nums[i] = nums[child];
i = child;
child = 2*i+1;
}
nums[i] = temp;
}
//==========>归并排序
private void mergeSort(int[] nums,int left,int right,int[] temp){
if(left >= right) return;
int mid = left + (right - left) / 2;
mergeSort(nums,left,mid,temp);
mergeSort(nums,mid+1,right,temp);
mergeLR(nums,left,mid,right,temp);
}
private void mergeLR(int[] nums,int left,int mid,int right,int[] temp){
int i = left, j = mid+1, tempIndex = left;
while(i <= mid && j <= right)
temp[tempIndex++] = nums[i] <= nums[j] ? nums[i++] : nums[j++];
while(i <= mid) temp[tempIndex++] = nums[i++];
while(j <= right) temp[tempIndex++] = nums[j++];
for(int k = left ; k <= right ; k++) nums[k] = temp[k];
}
//==========>基数排序 (防极端溢出：19桶)
private void radixSort(int[] nums){
int n = nums.length;
//先找出最大绝对值，可以明确最大位数及循环次数
int maxAbs = 0;
for(int i = 0 ; i < n ; i++){
maxAbs = Math.max(Math.abs(nums[i]),maxAbs);
}
int[] temp = new int[n];
//依次排序处理每位
for(long exp = 1 ; exp <= maxAbs ; exp *= 10){
countingForRadixSort(nums,exp,temp);
}
}
private void countingForRadixSort(int[] nums,long exp,int[] temp){
int[] count = new int[19];
int n = nums.length;
//各数出现频次
for(int i = 0 ; i < n ; i++){
int radix = (int)(nums[i] % (10 * exp) / exp) + 9;
count[radix]++;
}
//频次转前缀和
for(int i = 1 ; i < 19 ; i++){
count[i] += count[i-1];
}
//依据前缀和进行排序并放置
for(int i = n-1 ; i >= 0 ; i--){
int radix = (int)(nums[i] % (10 * exp) / exp) + 9;
temp[--count[radix]] = nums[i];
}
//替换原数组
for(int k = 0 ; k < n ; k++) nums[k] = temp[k];
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
