冒泡排序
时间复杂度：O(n^2) 空间复杂度O(1)
稳定性：稳定
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
private static void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length - 1; ++i) {
boolean swap = false;//利用标记，检测是否进行过交换
for (int j = 0; j < arr.length - 1 - i; ++j) {
if (arr[j] > arr[j + 1]) {
swap = true;
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
if (!swap) { //如果swap认为false，没有发生过交换，数组有序，结束程序
return;
}
}
}
优化后的冒泡排序，避免了数组有序后无用的比较。
选择排序
首先在未排序序列中找到最大元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最大元素，然后放到已排序序列的末尾。
以此类推，直到所有元素均排序完毕。
- 从未排序序列中，找到关键字最大的元素
- 如果最大元素不是未排序序列的第一个元素，将其和未排序序列第一个元素互换
- 重复1、2步，直到排序结束。
稳定性：不稳定
时间复杂度O(n^2) 空间复杂度O(1)
public static void choiceSort(int[]arr) {
for (int i = 0; i < arr.length - 1; i++) {
int k=i;int temp;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] <arr[k]) {
k=j;
}
}
if (k != i) {
temp = arr[i];
arr[i] = arr[k];
arr[k] = temp;
}
}
}
插入排序
直接插入排序
在一组基本有序的序列中，进行排序操作，插入排序效率是最高的
时间复杂度：O(n^2) 空间复杂度： O(1)
稳定性：稳定从数组下标1开始进行遍历；跟前一项进行对比，如果小于前一项，退出本次循环，进行下一次循环。
如果大于前一项，将前一项后移一位，继续跟前一项对比，直到小于前一项，退出本次循环，将空缺的位置补上。
public static void insertSort(int[]arr) {
for (int i = 1; i < arr.length; i++) {
int val = arr[i];
int j = i - 1;
for (; j >= 0; --j) {
if (val < arr[j]) {
arr[j + 1] = arr[j];
} else break;
}
arr[j + 1] = val;
}
}
改进插入排序
利用二分查找法 寻找一个合适的插入位置，可以减少比较过程，提高效率
public static void insertSort(int []arr) {
for (int i = 1; i < arr.length; i++) {
int temp = arr[i];
int j = i;
//二分查找寻找合适的插入位置
int first = 0;
int last = j-1;
while (first <=last) {
int middle = (first + last) / 2;
if (arr[j] < arr[middle]) {
last = middle - 1;
} else if (arr[j] > arr[middle]) {
first = middle + 1;
}
}
while (j>first){
arr[j]=arr[j-1];
j--;
}
arr[first] = temp;
}
}
快排
稳定性 ：不稳定
时间复杂度：O(log2 n） 最差情况：O（n^2）
快排的优化措施：
1.当数据范围小到一定程度时，采用插入排序代替快排
2.选择合适的基准数字（随机数法）（三数取中）快速排序的基本思想：挖坑填数+分治法。
快速排序使用分治策略来把一个序列分为两个子序列。
- 从数列中挑出一个元素，称为”基准”。
- 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
- 递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。
public static void quickSort(int[]arr,int i,int j){ if(i>j)
return;
int l=partation(arr,i,j);
quickSort(arr,i,l-1);
quickSort(arr,l+1,j);
}
private static int partation(int[] arr, int i, int j) {
int temp=arr[i];
while (i<j){
while (i<j&&arr[j]>temp) {
j--;
}
//从j开始找第一个小于temp的值
if (i<j) {
arr[i]= arr[j];
i++;
}
while (i<j&&arr[i]<temp) {
i++;
}
//从i+1号元素找比temp大的值
if (i<j) {
arr[j] = arr[i];
j--;
}
}
arr[i]=temp;
return i;
}
