参考链接：https://zhuanlan.zhihu.com/p/42586566
image.png
排序算法稳定性： 在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中r[i] = r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
快速排序
public static void quickSort(int[] arr){
qsort(arr, 0, arr.length-1);
}
private static void qsort(int[] arr, int low, int high){
if (low >= high)
return;
int pivot = partition(arr, low, high); //将数组分为两部分
qsort(arr, low, pivot-1); //递归排序左子数组
qsort(arr, pivot+1, high); //递归排序右子数组
}
private static int partition(int[] arr, int low, int high){
int pivot = arr[low]; //基准
while (low < high){
while (low < high && arr[high] >= pivot){
--high;
}
arr[low]=arr[high]; //交换比基准小的记录到左端
while (low < high && arr[low] <= pivot){
++low;
}
arr[high] = arr[low]; //交换比基准大的记录到右端
}
//扫描完成，基准到位
arr[low] = pivot;
//返回的是基准的位置
return low;
}
归并排序
- 自顶向下
- 自底向上
public static void mergeSort(int[] nums){
// mSortUpDown(nums, 0, nums.length-1);
mSortBottomUp(nums);
}
// 自顶向下-递归
public static void mSortUpDown(int[] nums, int left, int right){
if(left<=right){
return;
}
int mid = left + (right-left)/2;
mSortUpDown(nums, left, mid);
mSortUpDown(nums, mid+1, right);
merge(nums, left, mid, right);
}
// 自底向上-迭代
// 参考 https://juejin.cn/post/6844903935161925645
public static void mSortBottomUp(int[] nums){
int len = nums.length;
for(int size=1;size<len;size*=2){
//right的开始索引=left+size
for(int left=0;left<len-size;left+=size*2){
merge(nums, left, left+size-1, Math.min(left+size*2-1,len-1));
}
}
}
public static void merge(int[] nums, int left, int mid, int right){
int p1=left;
int p2=mid+1;
int index = 0;
int[] temp = new int[right-left+1];
while(p1<=mid && p2<=right){
if(nums[p1]<nums[p2]){
temp[index]=nums[p1];
p1++;
}else{
temp[index]=nums[p2];
p2++;
}
index++;
}
while(p1<=mid){
temp[index]=nums[p1];
p1++;
index++;
}
while(p2<=right){
temp[index]=nums[p2];
p2++;
index++;
}
for(int i=0;i<temp.length;i++){
nums[left+i]=temp[i];
}
}
堆排序
如果是从小到大原地排序，建立大顶堆，把堆顶即最大的元素与最后一位元素交换，然后对前n-1位调整堆，重复前面步骤。
public static void main(String[] args) {
int[] nums = {3,4,1,2,7,9,0};
heapSort(nums);
}
public static void heapSort(int[] nums){
int len = nums.length;
buildMaxHeap(nums, len);
while(len>1){
swap(nums, 0, len-1);
siftDown(nums, 0, len-1);
len--;
}
}
public static void buildMaxHeap(int[] nums, int len){
// 自下而上的下滤
for(int i=len/2-1;i>=0;i--){
siftDown(nums, i, len);
}
//自上而下的上滤
// for(int i=1;i<n;i++){
// siftUp(nums, i);
// }
}
public static void siftDown(int[] nums, int index, int len){
int n = len;
int element = nums[index];
while(index < n/2){
int childIdx = 2*index+1;
int child = nums[childIdx];
if(2*index+2<n){
int rightIdx = 2*index+2;
int right = nums[rightIdx];
if(right>child){
child=right;
childIdx=rightIdx;
}
}
if(child>element){
nums[index] = child;
index = childIdx;
}else{
break;
}
}
nums[index] = element;
}
public static void swap(int[] nums, int i, int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
计数排序
参考《恋上数据结构与算法》和 https://zhuanlan.zhihu.com/p/42586566
protected void countSort() {
// 找出最值
int max = array[0];
int min = array[0];
for (int i = 1; i < array.length; i++) {
if (array[i] > max) {
max = array[i];
}
if (array[i] < min) {
min = array[i];
}
}
// 开辟内存空间，存储次数
int[] counts = new int[max - min + 1];
// 统计每个整数出现的次数
for (int i = 0; i < array.length; i++) {
counts[array[i] - min]++;
}
// 累加次数
for (int i = 1; i < counts.length; i++) {
counts[i] += counts[i - 1];
}
int[] newArray = new int[array.length];
//将元素放到有序数组中的合适位置
for (int i = 0; i < array.length; i++) {
int num = array[i];//源数组第i位的值
int index = count[num - min] - 1;//加总数组中对应元素的下标
newArray[index] = num;//将该值存入存储数组对应下标中
count[num - min]--;//加总数组中，该值的总和减少1。
}
// 从后往前遍历元素，将它放到有序数组中的合适位置
//for (int i = array.length - 1; i >= 0; i--) {
// newArray[--counts[array[i] - min]] = array[i];
//}
// 将有序数组赋值到array
for (int i = 0; i < newArray.length; i++) {
array[i] = newArray[i];
}
}
桶排序
桶排序又叫箱排序，是计数排序的升级版，它的工作原理是将数组分到有限数量的桶子里，然后对每个桶子再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序），最后将各个桶中的数据有序的合并起来。
public static void bucketSort(int[] arr){
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for(int i = 0; i < arr.length; i++){
max = Math.max(max, arr[i]);
min = Math.min(min, arr[i]);
}
//桶数
int bucketNum = (max - min) / arr.length + 1;
ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
for(int i = 0; i < bucketNum; i++){
bucketArr.add(new ArrayList<Integer>());
}
//将每个元素放入桶
for(int i = 0; i < arr.length; i++){
int num = (arr[i] - min) / (arr.length);
bucketArr.get(num).add(arr[i]);
}
//对每个桶进行排序
for(int i = 0; i < bucketArr.size(); i++){
Collections.sort(bucketArr.get(i));
}
System.out.println(bucketArr.toString());
}
