- 1.基本排序算法总结
- 1.1 冒泡排序
- 1.2 选择排序
- 1.3 插入排序
- 1.4 希尔排序
- 1.5 归并排序（递归）
- 1.6 快速排序(对冒泡排序的一种改进)
- 1.7 堆排序(大根堆，小根堆)
- 1.8 基数排序(空间换时间)
//1.冒泡排序
public int[] bubbleSort(int[] arr){
int len = arr.length;
boolean flag = false;//优化
for(int i = 0;i < len;i ++){
for(int j = 0;j < len - 1 - i;j ++){
if(arr[j + 1] < arr[j]){
flag = true;
int temp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = temp;
}
}
if(!flag){//在一趟排序中，一次交换都没有发生，说明是升序的
break;
}else{
flag = false;
}
}
return arr;
}
1.2 选择排序
//2.选择排序
public int[] selectionSort(int[] arr){
int len = arr.length;
for(int i = 0;i < len;i ++){
//预定的最小下标
int minIndex = i;
for(int j = i + 1;j < len;j ++){
if(arr[j] < arr[minIndex]){
minIndex = j;
}
}
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
return arr;
}
1.3 插入排序
//3.插入排序
public int[] insertionSort(int[] arr){
int len = arr.length;
//待插入的数
int insertVal = 0;
//待插入的下标
int insertIndex = 0;
for(int i = 1;i < len;i ++){
insertVal = arr[i];
insertIndex = i - 1;
while(insertIndex >= 0 && insertVal < arr[insertIndex]){
arr[insertIndex + 1] = arr[insertIndex];
insertIndex --;
}
arr[insertIndex + 1] = insertVal;
}
return arr;
}
1.4 希尔排序
为什么希尔排序要比冒泡，插入快，用逆序数来理解链接
//4.希尔排序（简单插入排序的改进）
//对交换式的希尔排序进行优化->移位式
public int[] shellSort(int[] arr) {
int len = arr.length;
//gap：增量
for (int gap = len / 2; gap > 0; gap /= 2) {
for (int i = gap; i < len; i++) {
int preIndex = i - gap;
int temp = arr[i];
while (preIndex >= 0 && temp < arr[preIndex]){
arr[preIndex + gap] = arr[preIndex];
preIndex -= gap;
}
arr[preIndex + gap] = temp;
}
}
return arr;
}
1.5 归并排序（递归）
//归并排序需要用到额外的空间
public int[] mergeSort(int[] arr){
int len = arr.length;
//辅助数组
int[] temp = new int[len];
Sort(arr,0,len - 1,temp);
return arr;
}
public void Sort(int[] arr, int left, int right, int[] temp) {
if (left < right) {
int mid = (left + right) / 2;
//向左递归进行分解
Sort(arr, left, mid, temp);
//向右递归进行分解
Sort(arr, mid + 1, right, temp);
//合并
merge(arr, left, mid, right, temp);
}
}
//合并两个有序数组
public void merge(int[] arr, int left, int mid, int right, int[] temp) {
//初始化i，左边有序序列的初始索引
int i = left;
//初始化j，右边有序序列的初始索引
int j = mid + 1;
//指向temp数组的当前索引
int t = 0;
//1.第一种情况
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[t ++] = arr[i ++];
} else {
temp[t ++] = arr[j++];
}
}
//2.第二种情况
while (i <= mid){
temp[t ++] = arr[i++];
}
while (j <= right){
temp[t++] = arr[j++];
}
//3.将temp复制到arr
t = 0;
int tempLeft = left;
while (tempLeft <= right){
arr[tempLeft ++] = temp[t ++];
}
}
1.6 快速排序(对冒泡排序的一种改进)
public static void quickSort(int[] arr,int left,int right){
int l = left;//左下标
int r = right;//右下标
int pivot = arr[(left + right) / 2];//中轴值
int temp = 0;//临时变量，交换时使用
//while循环的目的：比pivot小的值放到左边，比他大的值放到右边
while (l < r){
//从左边开始一直找，直到找到一个比pivot大的值
while (arr[l] < pivot){
l ++;
}
//从右边开始一直找，直到找到一个比pivot小的值
while (arr[r] > pivot){
r --;
}
//如果l >= r，说明此时pivot左边的值都比它小，右边的值都比它大
if (l >= r){
break;
}
//交换
temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
//这里是优化
//如果已经交换的两个数都等于pivot，会出现死循环
//arr[l] == pivot已经到达左边能够到达的最大限度，所以r --
if (arr[l] == pivot){
r --;
}
if (arr[r] == pivot){
l ++;
}
}
if (l == r){
l ++;
r --;
}
if (left < r){
quickSort(arr,left,r);
}
if (right > l){
quickSort(arr,l,right);
}
}
1.7 堆排序(大根堆，小根堆)
public static void heapSort(int[] array){
// 按照完全二叉树的特点，从最后一个非叶子节点开始，对于整棵树进行大根堆的调整
// 也就是说，是按照自下而上，每一层都是自右向左来进行调整的
// 注意，这里元素的索引是从0开始的
//i = array.length / 2 - 1 -> 找到第一个非叶子节点
//第一个非叶子结点 arr.length/2-1=5/2-1=1
for (int i = array.length / 2 - 1; i >= 0; i--) {
adjustHeap(array, i, array.length);
}
// 上述逻辑，建堆结束
// 下面，开始排序逻辑
for (int j = array.length - 1; j > 0; j--) {
// 元素交换
// 说是交换，其实质就是把大顶堆的根元素（最大元素），放到数组的最后；换句话说，
// 就是每一次的堆调整之后，都会有一个元素到达自己的最终位置
swap(array, 0, j);
// 元素交换之后，毫无疑问，最后一个元素无需再考虑排序问题了。
// 接下来我们需要排序的，就是已经去掉了部分元素的堆了，这也是为什么此方法放在循环里的原因
// 而这里，实质上是自上而下，自左向右进行调整的
adjustHeap(array, 0, j);
}
}
public static void adjustHeap(int[] array, int i, int length) {
// 先把当前元素取出来，因为当前元素可能要一直移动
int temp = array[i];
// 接下来的讲解，都是按照i的初始值为0来讲述的(最终i会等于0)
// 这一段很好理解，如果i=0；则k=1；k+1=2
// 实质上，就是根节点和其左右子节点进行比较，让k指向这个不超过三个节点的子树中最大的值
// 这里，必须要说下为什么k值是跳跃性的。
// 首先，举个例子，如果a[0] > a[1] && a[0]>a[2],说明0,1,2这棵树不需要调整，
// 那么，下一步该到哪个节点了呢？肯定是a[1]所在的子树了
// 也就是说，是以本节点的左子节点为根的那棵小的子树
// 而如果a[0]
// 而且肯定是从左子树开始调整的
// 所以，这里面的用意就在于，自上而下，自左向右一点点调整整棵树的部分，
// 直到每一颗小子树都满足大根堆的规律为止
for (int k = 2 * i + 1; k < length; k = 2 * k + 1) {
// 让k先指向子节点中最大的节点
if (k + 1 < length && array[k] < array[k + 1]) {
k++;
}
// 如果发现子节点更大，则进行值的交换
if (array[k] > temp) {
swap(array, i, k);
// 下面就是非常关键的一步了
// 如果子节点更换了，那么，以子节点为根的子树会不会受到影响呢？
// 所以，循环对子节点所在的树继续进行判断
i = k;
// 如果不用交换，那么，就直接终止循环了
} else {
break;
}
}
}
public static void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
1.8 基数排序(空间换时间)
//8.基数排序(空间换时间)
public static void baseSort(int[] arr){
//1.得到数组中最大数的位数
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max){
max = arr[i];
}
}
//最大数的长度
int maxLength = (max + "").length();
//用二维数组表示一个桶,桶的数量为10个，每个桶的容量是arr.length
int[][] bucket = new int[10][arr.length];
//为了记录每个桶中实际存放了多少个数据，定义一个一维数组来记录每个桶每次放入的数据个数
int[] bucketElementCounts = new int[10];
for (int i = 0,n = 1; i < maxLength; i++,n *= 10) {
//2.放入
for (int j = 0; j < arr.length; j++) {
int digitalElement = arr[j] / n % 10;
bucket[digitalElement][bucketElementCounts[digitalElement]] = arr[j];
bucketElementCounts[digitalElement] ++;
}
//3.依次将桶中元素取出，放到arr中，顺序是按照放入时那一位的顺序
int index = 0;
for (int k = 0; k < bucketElementCounts.length; k++) {
if (bucketElementCounts[k] != 0){
for (int l = 0; l < bucketElementCounts[k]; l++) {
arr[index ++] = bucket[k][l];
}
}
//!!!!!!!!!
bucketElementCounts[k] = 0;
}
}
}
