class Sort {
// 冒泡排序
public void sortByBubble(int[] nums) {
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j < nums.length - i - 1; j++) {
if (nums[j] > nums[j + 1]) {
int temp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = temp;
}
}
}
}
// 插入排序
public void sortByInsertion(int[] nums) {
for (int i = 1; i < nums.length; i++) {
int num = nums[i];
int index = -1;
for (int j = i - 1; j >= 0; j--) {
if (num < nums[j]) {
index = j;
} else {
break;
}
}
if (index == -1) {
continue;
}
for (int j = i; j > index; j--) {
nums[j] = nums[j - 1];
}
nums[index]= num;
}
}
// 选择排序
public void sortBySelection(int[] nums) {
for (int i = 0; i < nums.length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < nums.length; j++) {
if (nums[j] < nums[minIndex]) {
minIndex = j;
}
}
if (i != minIndex) {
int temp = nums[i];
nums[i] = nums[minIndex];
nums[minIndex] = temp;
}
}
}
// 归并排序
public void sortByMerge(int[] nums) {
mergeSort(nums, 0, nums.length - 1);
}
private void mergeSort(int[] nums, int begin, int end) {
if (begin >= end) {
return;
}
int mid = begin + ((end - begin) >> 1);
mergeSort(nums, begin, mid);
mergeSort(nums, mid + 1, end);
merge(nums, begin, mid, end);
}
private void merge(int[] nums, int left, int mid, int right) {
int[] temp = new int[right - left + 1];
int i = left;
int j = mid + 1;
int k = 0;
while (i <= mid && j <= right) {
temp[k++] = nums[i] < nums[j] ? nums[i++] : nums[j++];
}
while (i <= mid) {
temp[k++] = nums[i++];
}
while (j <= right) {
temp[k++] = nums[j++];
}
for (int l = 0; l < temp.length; l++) {
nums[left + l] = temp[l];
}
}
// 快速排序
public void sortByQuick(int[] nums) {
quickSort(nums, 0, nums.length - 1);
}
private void quickSort(int[] nums, int begin, int end) {
if (begin >= end) {
return;
}
int pivot = partition(nums, begin, end);
quickSort(nums, begin, pivot - 1);
quickSort(nums, pivot + 1, end);
}
private int partition(int[] nums, int begin, int end) {
int pivot = end;
int counter = begin;
for (int i = begin; i < end; i++) {
if (nums[i] < nums[pivot]) {
int temp = nums[counter];
nums[counter] = nums[i];
n
5F9F
ums[i] = temp;
counter += 1;
}
}
int temp = nums[counter];
nums[counter] = nums[pivot];
nums[pivot] = temp;
return counter;
}
// 计数排序，假设数字的范围是[0,99]
public void sortByCounter(int[] nums) {
int min = 0;
int max = 100;
int[] counter = new int[max - min];
for (int num : nums) {
counter[num] += 1;
}
int j = 0;
for (int k = 0; k < counter.length; k++) {
while (counter[k] > 0) {
nums[j++] = k;
counter[k] -= 1;
}
}
}
}