冒泡排序
比较相邻的两个数，把较大的往后排
每内循环一次将两个数较大的排在后面
每外循环一次将未排序的最大的数排在最后
for (int i = 0; i < array.length - 1; i++) {
for (int j = 0; j < array.length - i - 1; j++) {
if (array[j] > array[j + 1]) {
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
选择排序
每次内循环将未排序的第一个数与其后面所有的数依次比较，将小的放在前面
每次外循环可以排出最小的数放在最前
for (int i = 0; i < array.length - 1; i++) {
for (int j = i + 1; j < array.length; j++) {
if (array[i] > array[j]) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
}
频繁交换 array [ i ] 和被比较的数 array [ j ]
所以利用 minIndex 暂存内循环里最大的数的索引
内层循环完再和 array [ i ] 比较交换
for (int i = 0; i < array.length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < array.length; j++) {
if (array[minIndex] > array[j]) {
minIndex = j;
}
}
if (array[i] != array[minIndex]) {
int temp = array[i];
array[i] = array[minIndex];
array[minIndex] = temp;
}
}
插入排序
从数组的第二个元素开始循环将数组中的元素插入
插入的数与当前位置的数向前递减依次比较
for (int i = 1; i < array.length; i++) {
for (int j = i; j > 0; j--) {
if (array[j] < array[j - 1]) {
int temp = array[j];
array[j] = array[j - 1];
array[j - 1] = temp;
}
}
}
同样交换次数频繁
for (int i = 1; i < array.length; i++) {
//记录插入的元素值
int insertNode = array[i];
int j = i - 1;
//找插入的位置，向前依次与插入元素比较
while (j >= 0 && insertNode < array[j]) {
//如果比较元素j比插入元素insert大，就把j向后移一位
array[j + 1] = array[j];
j--;
}
//比较的元素j<插入元素insertNode --> 跳出循环,插在j的后面
array[j + 1] = insertNode;
}
快速排序
设第一个数为基准值，左右两个指针 i,j 向中间移动，j先动，j找到比基准值小的停下，i找到比基准值大的停下，两个交换，直到 i,j 相遇，这样基准值左边的都比他小，右边的都比他大；
基准值左右半部分继续使用这种思想排序
public int[] sort(int[] array) {
section(0, array.length - 1, array);
return array;
}
/**
* 分段 排序
*
* @param left 分段数组最左边元素索引
* @param right 分段数组最右边元素索引
*/
private void section(int left, int right, int[] arr) {
//当数组分成只有一个元素的时候，递归结束
if (left > right) {
return;
}
//最左最右两个指针，基准值mark默认为第一个
int i = left;
int j = right;
int mark = arr[left];
while (i != j) {
//先看右边，依次往左递减检索，检索到比基准数小的就停下
while (arr[j] >= mark && i < j) {
j--;
}
//再看左边，依次往右递增检索
while (arr[i] <= mark && i < j) {
i++;
}
//交换
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
//i和j相遇，交换这个元素和基准值
arr[left] = arr[i];
arr[i] = mark;
//左右两半部分继续递归
section(left, j - 1, arr);
section(j + 1, right, arr);
}
归并排序
将数组不断分成相等的两部分，为每一个子序列排序，然后再合并成一个数组
public int[] sort(int[] array) {
mergeSort(0, array.length - 1, array);
return array;
}
private void mergeSort(int left, int right, int[] arr) {
//当子序列中只有一个元素时结束递归
if (left < right) {
//划分子序列，对左右侧子序列进行递归排序，合并
int mid = (left + right) / 2;
mergeSort(left, mid, arr);
mergeSort(mid + 1, right, arr);
merge(left, mid, right, arr);
}
}
private void merge(int left, int mid, int right, int[] arr) {
//辅助数组
int[] tempArr = new int[arr.length];
//左半部分检索指针i; 右半部分检索指针j; 辅助数组存放指针k
int i = left;
int j = mid + 1;
int k = left;
//合并 两数组
while (i <= mid && j <= right) {
if (arr[i] < arr[j]) {
tempArr[k++] = arr[i++];
} else {
tempArr[k++] = arr[j++];
}
}
//如果一半数组选择结束完，直接将另一个数组剩下的元素添加到tempArr
while (i <= mid) {
tempArr[k++] = arr[i++];
}
while (j <= right) {
tempArr[k++] = arr[j++];
}
//把暂存数组复制到原数组
for (int l = left; l <= right; l++) {
arr[l] = tempArr[l];
}
}
希尔排序
将待排数组按照一定的间隔分组，每组进行组内排序（插入排序）
组内间隔不断减小，直到减小为1
为什么不直接使用插入排序：减少交换次数
public void sort(int[] array) {
//每组元素个数 (最开始分为两组)
int d = array.length / 2;
//当每组元素大于1时，进行插入排序
while (d >= 1) {
insertSort(array, d);
d /= 2;
}
}
/**
* 类似插入排序，只是插入排序增量是 1，这里增量是 d,把 1 换成 d 就可以了
*/
private void insertSort(int[] array, int d) {
//i从d到结尾：包含每组的最后一个元素，循环完这些次数，这次排序就结束
for (int i = d; i < array.length; i++) {
//insertNode 记录待插入元素
int insertNode = array[i];
//从这组数据的倒数第二个数开始比较
int j = i - d;
while (j >= 0 && insertNode < array[j]) {
//通过循环，逐个前移 d 位找到要插入的位置
array[j + d] = array[j];
j -= d;
}
//插入
array[j + d] = insertNode;
}
}
桶排序
把数组划分为大小想等的子区间（桶），桶可以用ArrayList，每个子区间去排序，最后合并
- 找出待排序数组中的最大值 max、最小值 min
- 创建桶，动态数组 ArrayList 作为桶，桶的数量为(max-min)/arr.length+1
- 遍历数组 arr，计算每个元素 array[i] 放的桶
- 每个桶各自排序
public void sort(int[] array) {
//找到最大最小值
int max = 0;
int min = 0;
for (int i : array) {
max = Math.max(max, i);
min = Math.min(min, i);
}
//创建桶
int bucketNum = (max - min) / array.length + 1;
ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
for (int i = 0; i < bucketNum; i++) {
bucketArr.add(new ArrayList<>());
}
//将array中的元素放入桶
for (int i : array) {
//计算放在第几个桶
int num = (i - min) / array.length;
bucketArr.get(num).add(i);
}
//每个桶内排序
for (ArrayList<Integer> integers : bucketArr) {
Collections.sort(integers);
}
//合并桶
int k = 0;
for (ArrayList<Integer> integers : bucketArr) {
for (Integer integer : integers) {
array[k] = integer;
k++;
}
}
}
基数排序
将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序