# 排序
排序算法啊。。这是个数组里面常用的一种东西。。但是我一直 （懒得去记） 没记住这个算法。。而且最近写的题目总是时间超时。。算法复杂度太高。。就是两个for套在了一起。。现在为了方便记忆~~(偷懒)~~ 现在总结一下几个常见的排序算法；
# 冒泡排序法
这个就是复杂度o(n^2^)的一种
#include<stdio.h>
int main()
{
int i,j,s=0,t,k,n=7,a[7]={9,2,4,6,5,1,8};
for(i=0;i<n;i++)
{
s=0;
for(j=0;j<n-i-1;j++)
{
if(a[j]>a[j+1])//从小到大
{
t=a[j];a[j]=a[j+1];a[j+1]=t;s=1;
}
}
if(s==0) break;
}
return 0;
}性质：1、时间复杂度：O(n2) 2、空间复杂度：O(1) 3、稳定排序 4、原地排序
# 选择排序法
同上为o(n^2^)的算法
#include<stdio.h>
int main()
{
int i,j,s=0,t,k,n=7,a[7]={9,2,4,6,5,1,8};
for(i=0;i<n-1;i++)
{
for(j=i+1,k=i;j<n;j++)
if(a[j]<a[k]) k=j;//从小到大
if(k!=i)
{
t=a[i];a[i]=a[k];a[k]=t;
}
}
for(i=0;i<n;i++)
{
printf("%d",a[i]);
}
return 0;
}性质：1、时间复杂度：O(n2) 2、空间复杂度：O(1) 3、非稳定排序 4、原地排序
# 快速排序法
这个就比较厉害了。。这个是算法复杂度O(nlogn)的算法。。就很不错
public class QuickSort {
2 public static int[] quickSort(int[] arr, int left, int right) {
3 if (left < right) {
4 //获取中轴元素所处的位置
5 int mid = partition(arr, left, right);
6 //进行分割
7 arr = quickSort(arr, left, mid - 1);
8 arr = quickSort(arr, mid + 1, right);
9 }
10 return arr;
11 }
12
13 private static int partition(int[] arr, int left, int right) {
14 //选取中轴元素
15 int pivot = arr[left];
16 int i = left + 1;
17 int j = right;
18 while (true) {
19 // 向右找到第一个小于等于 pivot 的元素位置
20 while (i <= j && arr[i] <= pivot) i++;
21 // 向左找到第一个大于等于 pivot 的元素位置
22 while(i <= j && arr[j] >= pivot ) j--;
23 if(i >= j)
24 break;
25 //交换两个元素的位置，使得左边的元素不大于pivot,右边的不小于pivot
26 int temp = arr[i];
27 arr[i] = arr[j];
28 arr[j] = temp;
29 }
30 arr[left] = arr[j];
31 // 使中轴元素处于有序的位置
32 arr[j] = pivot;
33 return j;
34 }
35 }性质：1、时间复杂度：O(nlogn) 2、空间复杂度：O(logn) 3、非稳定排序 4、原地排序
# 堆排序
这就是另一个O(nlogn)复杂度的排序算法
public class Head {
2 // 堆排序
3 public static int[] headSort(int[] arr) {
4 int n = arr.length;
5 //构建大顶堆
6 for (int i = (n - 2) / 2; i >= 0; i--) {
7 downAdjust(arr, i, n - 1);
8 }
9 //进行堆排序
10 for (int i = n - 1; i >= 1; i--) {
11 // 把堆顶元素与最后一个元素交换
12 int temp = arr[i];
13 arr[i] = arr[0];
14 arr[0] = temp;
15 // 把打乱的堆进行调整，恢复堆的特性
16 downAdjust(arr, 0, i - 1);
17 }
18 return arr;
19 }
20
21 //下沉操作
22 public static void downAdjust(int[] arr, int parent, int n) {
23 //临时保存要下沉的元素
24 int temp = arr[parent];
25 //定位左孩子节点的位置
26 int child = 2 * parent + 1;
27 //开始下沉
28 while (child <= n) {
29 // 如果右孩子节点比左孩子大，则定位到右孩子
30 if(child + 1 <= n && arr[child] < arr[child + 1])
31 child++;
32 // 如果孩子节点小于或等于父节点，则下沉结束
33 if (arr[child] <= temp ) break;
34 // 父节点进行下沉
35 arr[parent] = arr[child];
36 parent = child;
37 child = 2 * parent + 1;
38 }
39 arr[parent] = temp;
40 }
41 }性质：1、时间复杂度：O(nlogn) 2、空间复杂度：O(1) 3、非稳定排序 4、原地排序
# 桶排序
桶排序就是把最大值和最小值之间的数进行瓜分，例如分成 10 个区间，10个区间对应10个桶，我们把各元素放到对应区间的桶中去，再对每个桶中的数进行排序，可以采用归并排序，也可以采用快速排序之类的。
public class BucketSort {
2 public static int[] BucketSort(int[] arr) {
3 if(arr == null || arr.length < 2) return arr;
4
5 int n = arr.length;
6 int max = arr[0];
7 int min = arr[0];
8 // 寻找数组的最大值与最小值
9 for (int i = 1; i < n; i++) {
10 if(min > arr[i])
11 min = arr[i];
12 if(max < arr[i])
13 max = arr[i];
14 }
15 //和优化版本的计数排序一样，弄一个大小为 min 的偏移值
16 int d = max - min;
17 //创建 d / 5 + 1 个桶，第 i 桶存放 5*i ~ 5*i+5-1范围的数
18 int bucketNum = d / 5 + 1;
19 ArrayList<LinkedList<Integer>> bucketList = new ArrayList<>(bucketNum);
20 //初始化桶
21 for (int i = 0; i < bucketNum; i++) {
22 bucketList.add(new LinkedList<Integer>());
23 }
24 //遍历原数组，将每个元素放入桶中
25 for (int i = 0; i < n; i++) {
26 bucketList.get((arr[i]-min)/d).add(arr[i] - min);
27 }
28 //对桶内的元素进行排序，我这里采用系统自带的排序工具
29 for (int i = 0; i < bucketNum; i++) {
30 Collections.sort(bucketList.get(i));
31 }
32 //把每个桶排序好的数据进行合并汇总放回原数组
33 int k = 0;
34 for (int i = 0; i < bucketNum; i++) {
35 for (Integer t : bucketList.get(i)) {
36 arr[k++] = t + min;
37 }
38 }
39 return arr;
40 }
41 }性质：1、时间复杂度：O(n+k) 2、空间复杂度：O(n+k) 3、稳定排序 4、非原地排序
一会再写一个游记之类的东西。。。先写这么多。。快期末考试了。。恐惧。😨😨😨😨
