快速排序
快速排序是对冒泡排序的一种改进。通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另一部分所有的数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列
public static int[] quickSort(int[] arrs, int left, int right){
int l = left;
int r = right;
int middle = arrs[(left + right) / 2];
// l > r时两者相交
while (l < r){
// 找出左边比中间数大的值
while (arrs[l] < middle){
l++;
}
// 找出左边比中间数小的值
while (arrs[r] > middle){
r--;
}
// 如果 l>=r说明左边全部是小于pivot的值,右边全部是大于pivot的值
if (l >= r){
break;
}
// 交换
int temp = arrs[l];
arrs[l] = arrs[r];
arrs[r] = temp;
/**
* 作用:
* 2000,542,3,1,14,214,154,748,616
* 交换后
* 14,542,3,1,2000,214,154,748,616 || 此时l = 0, r = 4
* 下方递归时:
* quickSort(arrs, left, r); left = 0, r = 4
* 14,542,3,1,2000 || 初始l = 0 , right = 4
* 则会把2000与14再比较一次, r--呢就可以避开这次无意义的比较
* 简单来说就是一个小优化,加不加影响不大
*/
if (arrs[l] == middle){
r--;
}
if (arrs[r] == middle){
l++;
}
// 不错开就会无限循环了,arr[l] = 3, arr[r] = 3, l = r两者一直相同
if (l == r){
l++;
r--;
}
if (r > left){
quickSort(arrs, left, r);
}
if (l < right){
quickSort(arrs, l, right);
}
}
return arrs;
}
基数排序
public static int[] sort(int[] array){
int maxNum = array[0];
for (int i : array){
if (maxNum < i){
maxNum = i;
}
}
// 得到最大数是几位数
int maxSize = Integer.toString(maxNum).length();
// 0 - 9十个数,所有new int[10]
// array.length一共有这点数要存
int[][] bucket = new int[10][array.length];
// 记录每个桶中实际存放了多少个数据,比如 个位=5 的数存放了 10个,则bucketCount[5] = 10
int[] bucketCount = new int[10];
for (int i = 0, n = 1; i < maxSize; i++, n *= 10){
for (int value : array) {
int locationNum = value / n % 10;
// bucketCount[locationNum] 表示放了该数字几个,可以用来作为坐标
// bucket[locationNum][bucketCount[locationNum]]存放的数是原来的数
bucket[locationNum][bucketCount[locationNum]] = value;
bucketCount[locationNum]++;
}
int index = 0;
// 按照桶顺序将值放入
for (int j = 0; j < bucketCount.length; j++){
if (bucketCount[j] != 0){
for (int k = 0; k < bucketCount[j]; k++) {
array[index++] = bucket[j][k];
}
}
bucketCount[j] = 0;
}
}
return array;
}