1、冒泡排序
说明:
1、比较相邻的元素。如果第一个比第二个大，就交换它们两个
2、对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
3、依次比较，这里注意，比如说第一轮比较完成后，最后一个已经是最大的了，第二轮就不需要在比较了
时间复杂度 暂时空着
代码实现
public static int[] sort_maopao(int[] a) {
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a.length-1-i; j++) {
if (a[j] > a[j + 1]) {
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
return a;
}
2、选择排序
说明:
1、首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
2、n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果
3、初始状态：无序区为R[1..n]，有序区为空；
4、第一次排序将无序区所有数依次比较，选出最小的放到第一位，这是有序区为R[1],无序区是
R[2.n],在无序区中选出最小的放到第二位，并将第二位的数的下标与最小的数值的下标进行替换
时间复杂度: 暂时空着
代码实现
public static int[] sort_xuanze(int[] arr) {
for(int i=0;i<arr.length-1;i++){
int tmp;
int minIndex =i;
for(int j=i+1;j<arr.length;j++){
if (arr[j]<arr[minIndex]){
minIndex=j;
}
}
tmp=arr[i];
arr[i]=arr[minIndex];
arr[minIndex]=tmp;
}
return arr;
}
3、插入排序
说明:
1、通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
2、从第一个元素开始，该元素可以认为已经被排序；
3、取出下一个元素，在已经排序的元素序列中从后向前扫描；
4、如果该元素（已排序）大于新元素，将该元素移到下一位置；
5、重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
6、将新元素插入到该位置后；
7、重复步骤3~6。
时间复杂度: 暂时空着
代码实现
public static int[] sort_charu(int[] arr){
int len = arr.length;
int preIndex, current;
for (int i = 1; i < len; i++) {
preIndex = i - 1;
current = arr[i];
while (preIndex >= 0 && arr[preIndex] > current) {
arr[preIndex + 1] = arr[preIndex];
preIndex--;
}
arr[preIndex + 1] = current;
}
return arr;
}
4、计数排序
说明：
1、计数排序需要先比较一下所有数的最大值max和最小值min
2、计数排序的时间复杂度是O(n)
3、建立一个数组的长度是max-min+1
4、计数排序对于实数的排序是不可行的，因为1,2之间可能有无限个数
实现代码如下
public static int[] jishu(int[] arr){
int min=0; int max=0;int bi=0;
int[] c;
int[] b=new int[arr.length];
//便利所有数，找最大最小值
for(int i=0;i< arr.length;i++){
if (arr[i]<min){
min=arr[i];
}
if (arr[i]>max){
max=arr[i];
}
}
c=new int[max-min+1];
//遍历原数组，c数组下表的值即arr[i]-min
for (int i=0;i<arr.length;i++){
c[arr[i]-min]++;
}
//将c数组遍历，将结果放到b数组
for(int i=0;i<c.length;i++){
while (c[i]>0){
b[bi]=i+min;
c[i]--;
bi++;
}
}
return b;
}
