排序算法归纳
- 稳定排序：相等值不交换，包括冒泡、插入、归并和基数
- 不稳定排序：相等值交换，包括选择，快排序，希尔，堆排序
复杂度
思路
- 冒泡
相邻两个交换，每次循环让当前与前一个比较，如果不满足顺序则交换 - 插入
前面的已经排序好，把当前的值插入到前面的有序序列中，代码是 从当前逐步向前回溯交换 - 归并
分割序列，把当前序列平均分割为两个序列，然后分别对这两个序列进行排序，然后合并成一个序列，对于两个有序序列，只需要遍历一遍就可以得到一个有序。递归的执行，最终最小的数组是1个元素或者0个元素，逐步的合并。 - 基数排序
对数字进行排序，建立0-9数字桶，对于一个数字，把他拆分为为多个数字，从低位到高位逐位放入数字桶中
选择排序
前面是有序的，选择当前值作为后面序列中的最小值。每次循环找到未排序序列的最小值快排序
分治，对于每一个子序列，选择一个基准，把小于基准的数放到左边，大于基准的数放到右边，快排在于基准的选择，一般采用随机选择。希尔排序
多路插入排序，对原数组进行分组，这里分组与归并的分组并不相同，归并的每个分组是连续的。这里并不是连续的。
希尔排序按照隔一段距离gap取一个数作为分组的元素。对每一个分组只执行一次插入排序，认为分组序列除了最后一位都是有序的堆排序
建立大顶堆，把根移除了并放入到有序数组中，通常放入到数组后面的有序部分，调整大根堆，反复进行。
代码
冒泡
//交换相邻
public static void bubble1(int[] input) {
for (int i = 0; i < input.length; i++) {
for (int j = 1; j < input.length; j++) {
if (input[j] < input[j - 1]) {
int temp = input[j - 1];
input[j - 1] = input[j];
input[j] = temp;
}
}
}
} 插入
//把当前值逐步向前移动到合适位置
public static void insert1(int[] input) {
for (int i = 1; i < input.length; i++) {
int current = input[i]; // 当前值
int pre = i - 1;
while (pre >= 0 && input[pre] > current) {
input[pre + 1] = input[pre]; //把前一个值往后面移动
pre--;
}
input[pre + 1] = current;
}
} 归并--递归实现
public static int[] mergeSort(int[] input) {
if (input.length <= 1) {
return input;
}
int len = input.length / 2; //分割左右数组
int[] left = Arrays.copyOfRange(input, 0, len);
int[] right = Arrays.copyOfRange(input, len, input.length);
left = mergeSort(left);
right = mergeSort(right);
return merge(left, right);
}
//把左右两边合并起来成为一个数组，左右两边都是有序的
public static int[] merge(int[] left, int[] right) {
int[] result = new int[left.length + right.length];
//i为left下标，j为right下标
for (int index = 0, i = 0, j = 0; index < result.length; index++) {
if (i >= left.length) {
result[index] = right[j++];
} else if (j >= right.length) {
result[index] = left[i++];
} else if (left[i] <= right[j]) {
result[index] = left[i++];
} else {
result[index] = right[j++];
}
}
return result;
}归并--非递归实现
public static void mergetSort(int[] input) {
if (input.length <= 1) {
return;
}
int len = 1;
while (len < input.length) {
int start = 0;
while (start + 2 * len - 1 < input.length) {
int mid = start + len - 1;
int end = start + 2 * len - 1;
merge(input, start, mid, end);
start = start + 2 * len;
}
//剩余无法构成完整的两组也要进行处理
if (start + len - 1 < input.length)
merge(input, start, start + len - 1, input.length - 1);
len = len * 2;
}
}
public static void merge(int[] arr, int start, int mid, int end) {
int i = start;
int j = mid + 1;
int[] temp = new int[end - start + 1];
int index = 0;
while (i <= mid && j <= end) {
if (arr[i] <= arr[j])
temp[index++] = arr[i++];
else
temp[index++] = arr[j++];
}
while (i <= mid)
temp[index++] = arr[i++];
while (j <= end)
temp[index++] = arr[j++];
for (int k = start; k <= end; k++)
arr[k] = temp[k - start];
}
选择排序
public void seclect1(int[] input) {
for (int i = 0; i < input.length; i++) {
//当前值
int index = i;
//找出从i->n的最小值
for (int j = i; j < input.length; j++) {
if (input[j] < input[index]) {
index = j;
}
}
//最小值与当前值交换
int temp = input[index];
input[index] = input[i];
input[i] = temp;
}
}快速排序
/**
* 快速排序方法
*
* @param array
* @param start 0 ,调用起始值
* @param end len-1 ，调用终止值
*/
public static void quickSort(int[] array, int start, int end){
if(start < 0 || end >= array.length || start > end) return;
int smallIndex = partition(array, start, end);//分治界线
if(smallIndex > start){
quickSort(array, start, smallIndex - 1);//分治递归
}
if(smallIndex < end){
//System.out.println("debugright:" + smallIndex);
quickSort(array, smallIndex + 1, end);
}
}
/**
* 快速排序算法——partition,寻找分解点
*
* @param array
* @param start
* @param end
* @return
*/
public static int partition(int[] array, int start, int end){
//基准
int pivot = (int) (start + Math.random() * (end - start + 1));//在start和end之间随机选择一个值作为标准
int smallIndex = start - 1; //小于基准的指针，标记基准的左边
swap(array, pivot, end);//将基准准放在end位置
for(int i = start; i <= end; i++)
//如果当前值小于基准值，那么基准指针向右走一步
{
if(array[i] <= array[end]){
smallIndex++;
// 当前值小于基准，进而判断当前值是否在基准的左边，
// i>samllIndex 把当前值与边界交换，smallIndex++已经对左边进行扩容
if(i > smallIndex)
swap(array, i, smallIndex);
}
}
return smallIndex;
}
/**
* 交换数组内两个元素
*
* @param array
* @param i
* @param j
*/
public static void swap(int[] array, int i, int j){
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}希尔排序
public void shellSort(int[] input) {
int gap = 1;
//初始分割间隔，len=9=>gap=4
while (gap < input.length / 3) {
gap = gap * 3 + 1;
}
System.out.println("input.len="+input.length);
while (gap >= 1) {
System.out.println("gap:"+gap);
// 开始一次插入排序，认为每个分组除了最后一位都是有序的
for (int i = gap; i < input.length; i++) {
int tmp = input[i]; //当前值
int j = i - gap;
while (j >= 0 && input[j] > tmp) {
input[j + gap] = input[j];
j -= gap;
}
input[j + gap] = tmp;
}
gap = gap / 3;
System.out.println(Arrays.toString(input));
}
}堆排序
public static void heapSort(int[] arr) {
System.out.println("堆排序");
//构建大顶堆
for(int i = arr.length / 2 - 1; i >= 0; i--){
adjustHeap(arr, i, arr.length);
}
//堆调整
int temp;
//将root元素与最后交换
for(int i = arr.length - 1; i > 0; i--){
//交换
temp = arr[i]; //i表示大顶堆的叶子结点，arr[0-i]存储这个大顶堆。
arr[i] = arr[0];
arr[0] = temp;
adjustHeap(arr, 0, i);
}
System.out.println(Arrays.toString(arr));
}
//堆的调整
public static void adjustHeap(int[] arr, int i, int len) {
int temp = arr[i];
// 第i个的左子节点为2i+1
for(int k = 2 * i + 1; k < len; k = 2 * k + 1){
//k指针指向左右节点较大的那个子结点
if(k + 1 < len && arr[k] < arr[k + 1]) {
k++;
}
if(arr[k] > arr[i]) {
arr[i] = arr[k];
i = k; //i 指向 k //注意 ，i
} else { //子结点小于父节点
break; //for循环结束之后，已经将以i为父结点的树的最大值放在的最顶（局部）
}
}
arr[i] = temp;
}基数排序
public static int[] sort(int[] sourceArray) {
// 对 arr 进行拷贝，不改变参数内容
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
int maxDigit = getMaxDigit(arr);
return radixSort(arr, maxDigit);
}
/**
* 获取最高位数
*/
private static int getMaxDigit(int[] arr) {
int maxValue = getMaxValue(arr);
return getNumLenght(maxValue);
}
// 获得最大值
private static int getMaxValue(int[] arr) {
int maxValue = arr[0];
for (int value : arr) {
maxValue=Math.max(maxValue,value);
}
return maxValue;
}
// 获得最大度位数
protected static int getNumLenght(long num) {
if (num == 0) {
return 1;
}
int lenght = 0;
for (long temp = num; temp != 0; temp /= 10) {
lenght++;
}
return lenght;
}
//基数排序
private static int[] radixSort(int[] arr, int maxDigit) {
int mod = 10;
int dev = 1;
for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
// 考虑负数的情况，这里扩展一倍，其中 [0-9]对应负数，[10-19]对应正数 (bucket + 10)
int[][] counter = new int[mod * 2][0]; //二维数组，列初始值为0，通Append实现保存并扩容
for (int j = 0; j < arr.length; j++) {
int bucket = ((arr[j] % mod) / dev) + mod; //+10是把负数变成正数
counter[bucket] = arrayAppend(counter[bucket], arr[j]);
}
int pos = 0;
for (int[] bucket : counter) {
for (int value : bucket) {
arr[pos++] = value;
}
}
}
return arr;
}
/**
* 自动扩容，并保存数据
*
* @param arr
* @param value
*/
private static int[] arrayAppend(int[] arr, int value) {
arr = Arrays.copyOf(arr, arr.length + 1);
arr[arr.length - 1] = value;
return arr;
}
京公网安备 11010502036488号