排序算法
1. 时间复杂度分析
不稳定的有：选择排序、希尔排序、快速排序、堆排序
In-place占用常数内存，不占用额外内存
Out-place: 占用额外内存
稳定性：如果a=b,a在b的前面，排序过后a还是在b的前面
图片引用
2. 冒泡排序
/**
* 冒泡排序
* @param arrays 需要排序的数组
* @return 排序后的结果
* @description
* 1. 比较相邻的元素。如果第一个比第二个大，就交换它们两个。
* 2. 每次比较过后，最大的元素就会在数组的末尾。
*/
public int[] bubbleSort(int[] arrays) {
int n = arrays.length;
if (n == 0)
return arrays;
for (int i = 0; i < n; i++) { // 第一个循环是次数
for (int j = 0; j < n - 1 - i; j++) { // 第二次循环是最大元素往数组末尾移动
if (arrays[j + 1] < arrays[j]) {
int temp = arrays[j + 1];
arrays[j + 1] = arrays[j];
arrays[j] = temp;
}
}
}
return arrays;
}
3. 选择排序
/**
* 选择排序
* @param arrays
* @return
* @description
* 1. 依次从数组中选择最小的值 与 第一个值进行交换
*/
public int[] selectSort(int[] arrays){
int n = arrays.length;
if (n == 0)
return arrays;
for (int i = 0; i < n; i++) { // 第一次是循环次数
int minindex=i;
for (int j = i; j < n; j++) {
if (arrays[j] < arrays[i]) {//第二次是找到当前最小元素的索引。
minindex=j;
}
}
int t=arrays[minindex];
arrays[minindex]=arrays[i];
arrays[i]=t;
}
return arrays;
}
4. 归并排序
/**
* 归并排序，二分法合并，需要额外的空间
* @param arrays 待排序的数组
* @return
*/
public int[] MergeSort(int[] arrays) {
int n = arrays.length;
if (n < 2) return arrays;
merge(arrays, 0, n - 1,new int[n]);
return arrays;
}
/**
* 合并两个有序的数组
* @param arr
* @param left
* @param right
* @param tempt 用于合并两个有序数组的辅助数组
*/
public void merge(int[] arr, int left, int right,int[] tempt) {
if(left>=right) return;
int mid=left+(right-left)/2;
merge(arr,left,mid,tempt);
merge(arr,mid+1,right,tempt);
if(arr[mid]<=arr[mid+1]){ //本身有序不需要合并
return;
}
// 合并两个数组
int i = left, j = mid + 1;
int index = 0; //辅助数组的索引
while (i <= mid && j <= right) {
if (arr[i] < arr[j]) {
tempt[index++] = arr[i++];
}
else {
tempt[index++] = arr[j++];
}
}
while (i <= mid) tempt[index++] = arr[i++];
while (j <= right) tempt[index++] = arr[j++];
for (i = 0; i < right-left + 1; i++) {
arr[i + left] = tempt[i];
}
}
5. 快速排序
/**
* 快速排序
* @param arrays 待排序的数组
* @return
*/
public int[] quickSort(int[] arrays){
int n=arrays.length;
if(n<2) return arrays;
quickSort_(arrays,0,n-1);
return arrays;
}
/**
* 依次确定每个数据所在的位置，再分治
* @param arrays
* @param left
* @param right
*/
public void quickSort_(int[] arrays,int left,int right){
if(left>=right) return ;
int j=partition(arrays,left,right);
quickSort_(arrays,left,j-1);
quickSort_(arrays,j+1,right);
}
/**
* 确定left对应数据所在的位置
* @param arrays
* @param left
* @param right
* @return
*/
public int partition(int[] arrays,int left,int right){
int pivot=arrays[left];
while (left<right){
while (left<right && arrays[right]>=pivot) right--;
if(left<right){
arrays[left]=arrays[right];
}
while (left<right && arrays[left]<=pivot) left++;
if(left<right){
arrays[right]=arrays[left];
}
}
arrays[left]=pivot;
return left;
}
6. 堆排序
堆排序是一种选择排序，堆是具有以下性质的完全二叉树：：
* 每个结点的值都大于或等于其左右孩子结点的值，称为大根堆。
* 每个结点的值都小于或等于其左右孩子结点的值，称为小根堆。
升序采用大根堆；降序采用小根堆。
public int[] heapSort(int[] nums){
int n=nums.length;
for(int i=n/2-1;i>=0;i--){ // 从最后一个 非叶节点开始，遍历非叶结点
adjustHeap(nums,i,n);
}
// 堆顶元素跟尾巴节点 交换，然后调整 再交换
for(int i=n-1;i>0;i--){
swap(nums,0,i);// 堆顶节点 与末尾元素交换
adjustHeap(nums,0,i);// 然后调整堆
}
return nums;
}
public void swap(int[] nums,int left,int right){
int t=nums[left];
nums[left]=nums[right];
nums[right]=t;
}
// 调整大顶堆,找到该节点的孩子节点中最大那一个节点
public void adjustHeap(int[] nums,int index,int length){
int temp=nums[index];
for(int i=index*2+1;i<length;i=i*2+1){ // 从该节点的左孩子开始
if(i+1<length && nums[i]<nums[i+1]){
i++; // 如果左孩子小于右孩子
}
if(nums[i]>temp){ // 孩子节点值大于父节点
nums[index]=nums[i];
index=i;
}else {
break;
}
}
nums[index]=temp;
}
7. 计数排序
算法步骤:
- 找出待排序的数组中最大元素
- 创建一个数组count,长度为最大值加1,默认值为0
- 遍历原数组中的元素，以原数组中的元素作为count数组的索引;以原数组中的元素出现次数作为count数组的元素值
- 遍历count数组，找出其中元素值大于0的元素，将其对应的索引作为元素值填充到result数组中去, 每处理一次，count中的该元素值减1，直到该元素值不大于0.
特点:
当输入的元素是 n 个 0 到 k 之间的整数时，它的运行时间是 Θ(n + k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。
由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。
public void CountingSort(int[] nums){
int maxValue = Arrays.stream(nums).max().getAsInt();
int bucketLen = maxValue + 1;
int[] bucket = new int[bucketLen];
for (int value : nums) {
bucket[value]++;
}
int sortedIndex = 0;
for (int j = 0; j < bucketLen; j++) {
while (bucket[j] > 0) {
nums[sortedIndex++] = j;
bucket[j]--;
}
}
}
8. 桶排序
思想:
把数据划分到多个范围相同的区间,每个子区间自排序，最后合并.
需要确定桶的个数,每个桶的取值范围,和映射函数.
public void bucketSort(int[] nums){
int n=nums.length;
int maxValue = Arrays.stream(nums).max().getAsInt();
int minValue = Arrays.stream(nums).min().getAsInt();
int bucketNum = (maxValue - minValue) /n + 1;
ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
for(int i = 0; i < bucketNum; i++){
bucketArr.add(new ArrayList<>());
}
// 将每个元素放入桶
for(int i = 0; i < n; i++){
int num = (nums[i] - minValue) / n; //判断被分到那一个桶
bucketArr.get(num).add(nums[i]);
}
// 对每个桶进行排序
for(int i = 0; i < bucketArr.size(); i++){
Collections.sort(bucketArr.get(i));
}
// 将桶中的元素赋值到原序列
int index = 0;
for(int i = 0; i < bucketArr.size(); i++){
for(int j = 0; j < bucketArr.get(i).size(); j++){
nums[index++] = bucketArr.get(i).get(j);
}
}
}
9. 基数排序
LSD基数排序基本思想:
- 对于一组数据,先按个位数的值把数据分到9个桶,然后重新串联起来;
- 再按十位数的数值把数据分到9个桶里,再串联起来;
- 直到数据有序.
LSD的基数排序适用于位数小的数列，如果位数多的话，使用MSD的效率会比较好。
MSD的方式与LSD相反，是由高位数为基底开始进行分配，但在分配之后并不马上合并回一个数组中，而是在每个“桶子”中建立“子桶”，将每个桶子中的数值按照下一数位的值分配到“子桶”中。在进行完最低位数的分配后再合并回单一的数组中。
/**
*
* @param nums 待排序的数
*/
public void LsdSort(int[] nums){
int n=nums.length;
long exp = 1;
int[] buf = new int[n];
int maxVal = Arrays.stream(nums).max().getAsInt(); // 最大值
while (maxVal >= exp) {
int[] cnt = new int[10]; // 用来存放个数
for (int i = 0; i < n; i++) {
int digit = (nums[i] / (int) exp) % 10;
cnt[digit]++;
}
// 这一步的目的，是记录当前桶的数据，在buffer里面可以存放的位置
for (int i = 1; i < 10; i++) {
cnt[i] += cnt[i - 1];
}
for (int i = n - 1; i >= 0; i--) {
int digit = (nums[i] / (int) exp) % 10;
buf[cnt[digit] - 1] = nums[i];
cnt[digit]--;
}
System.arraycopy(buf, 0, nums, 0, n);
exp *= 10;
}
}
10. 希尔排序
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
/**
* 希尔排序
* @param arrays
* @return
*/
public int[] xiersort(int[] arrays){
for(int gap=arrays.length/2;gap>0;gap=gap/2){
for(int i=gap;i<arrays.length;i++){
int j=i;
while (j-gap>=0 && arrays[j]<arrays[j-gap] ){
int t=arrays[j];
arrays[j]=arrays[j-gap];
arrays[j-gap]=t;
j-=gap;
}
}
}
return arrays;
}
快速排序为什么比堆排序好？
用堆排序(大根堆做升序排序)的时候，每次找到最大的元素放在堆顶，然后将他移除掉放在末尾，末尾元素又放在堆顶，但是被放到堆顶的那个末尾元素几乎肯定是很小的，而靠近堆顶的元素又几乎肯定是很大的，所以被放到堆顶的那个元素能留在堆顶的可能性很小，很有可能又会回到堆的底部，所以在堆排序里面有大量这种近乎无效的比较，当数据量大时，比较所花费的时间开销 越来越大。
而快速排序，每次数据移动都意味着该数据距离它正确的位置越来越近。而在堆排序中，类似将堆尾部的数据移到堆顶这样的操作只会使相应的数据远离它正确的位置。