SortAlgorithm
大约 8 分钟
Sort Algorithm： BubbleSort、SelectionSort、InsertSort
SortAlgorithm
一、BubbleSort
基本思想：
相邻的元素两两比较，较大的数下沉，较小的数冒起来，这样一趟比较下来，最大(小)值就会排列在一端。 就像水底下的气泡一样逐渐向上冒
- 冒泡排序的原理：
每一趟只能确定将一个数归位。即第一趟只能确定将末位上的数归位，第二趟只能将倒数第 2 位上的数归位，依次类推下去。如果有 n 个数进行排序，只需将 n-1 个数归位，也就是要进行 n-1 趟操作。 而 “每一趟 ” 都需要从第一位开始进行相邻的两个数的比较，将较大的数放后面，比较完毕之后向后挪一位继续比较下面两个相邻的两个数大小关系，重复此步骤，直到最后一个还没归位的数。
在冒泡排序中，遇到相等的值，是不进行交换的，只有遇到不相等的值才进行交换，所以是
稳定的排序方式。时间复杂度：o(n^2)，空间复杂度O(1)
// 一般冒泡排序
public static void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - i - 1; j++) {
int temp;
if(arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
//优化方式一：在某趟排序中，没有发生一次交换，则说明数组中元素已经有序。
/*但同时也存在着缺点：某趟比较只要开始，哪怕数组元素已经有序，也要把该趟的所有次比较完。
*也就是说，第一种优化方式，只能在“趟”的级别上优化。
*/
public static void bubbleSort2(int[] arr) {
System.out.println(Arrays.toString(arr));
int temp;
boolean flag = false; // 某趟是否发生过交换
// 进行 n - 1 躺
for (int i = 0; i < arr.length - 1; i++) {
// 每躺比较的个数
for (int j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
flag = true;
temp = arr[j+1];
arr[j+1] = arr[j];
arr[j] = temp;
}
}
if (!flag) {
break;
} else {
flag = false;
}
}
}
//优化方式二：实现在“次”的级别进行优化，其思路是“记下最后一次交换的位置，后边没有交换，必然是有序的，
//然后下一次排序从第一个比较到上次记录的位置结束即可” 例如： 1 5 4 2 3 8 9 10 不需要对8之后进行比较
public static void bubbleSorted3(int[] arr) {
int position; // 初始时记录数组中的最后一次交换的位置
int k = arr.length - 1;
boolean isSwap;
for(int i = 0; i < arr.length - 1; i++) {
position = 0;
isSwap = false;
for (int j = 0; j < k; j++) {
//交换
if (arr[j] > arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
position = j;
isSwap = true;
}
}
//同优化方式一： 若某躺中没有发生交换，数组已经有序
if (!isSwap) {
return;
}
k = position;
}
}
//优化方式三：双向遍历（也叫鸡尾酒排序）
//正向循环把最大元素移动到数组末尾，逆向循环把最小元素移动到数组首部
//优化需要结合第二种优化方式，对于前后部分有序的情况下就可以直接进行中间部分的排序
// 例如： 1 2 3 4 10 7 8 9 12 13 14 15
public static void bubbleSort(int[] array) {
int arrayLength = array.length;
int preIndex = 0;
int backIndex = arrayLength - 1;
while(preIndex < backIndex) {
preSort(array, arrayLength, preIndex);
preIndex++;
if (preIndex >= backIndex) {
break;
}
backSort(array, backIndex);
backIndex--;
}
}
// 从前向后排序
public static void preSort(int[] array, int length, int preIndex) {
for (int i = preIndex + 1; i < length; i++) {
if (array[preIndex] > array[i]) {
swap(array, preIndex, i);
}
}
}
// 从后向前排序
public static void backSort(int[] array, int backIndex) {
for (int i = backIndex - 1; i >= 0; i--) {
if (array[i] > array[backIndex]) {
swap(array, i, backIndex);
}
}
}
public static void swap (int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
二、SelectionSort
第一次从待排序的中数据元素选出最小（或最大）的一个元素，存放在序列的起始位置，
然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。
以此类推，直到全部待排序的数据元素的个数为零。
选择排序是
不稳定的排序方法。{ 在选择排序中，每趟都会选出最大元素或最小元素，然后与两端元素交换，
此时，待排序序列中如果存在与原来两端元素相等的元素，稳定性就可能被破坏。
如[5,3,5,2,9]，在array[0]与array[3]元素交换时，序列的稳定性就被破坏了，所以选择排序是一种不稳定的排序算法。}
分析： n个数据有 n-1 轮排序，每轮排序需确定最小的数据的下标，设第一个为最小的数，需进行判断 n-i次
public static void selectionSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++)
{
int minIndex = i;
int min = arr[i];
for (int j = i + 1; j < arr.length; j++)
{
//在第一次中找出最小的数和其对应的下标
if (min > arr[j]) {
min = arr[j];
minIndex = j;
}
}
// 如果最小的不是第一个，就交换这两个数
if (minIndex != i) {
arr[minIndex] = arr[i];
arr[i] = min;
}
}
}
//优化：在一趟遍历中，同时找出最大值与最小值，放到数组两端，这样就能将遍历的趟数减少一半
/*初始化左端、右端元素索引*/
int left = 0;
int right = len - 1;
while (left < right){
/*初始化最小值、最大值元素的索引*/
int min = left;
int max = right;
for (int i = left; i <= right; i++){
/*标记每趟比较中最大值和最小值的元素对应的索引min、max*/
if (arr[i] < arr[min])
min = i;
if (arr[i] > arr[max])
max = i;
}
/*最大值放在最右端*/
int temp = arr[max];
arr[max] = arr[right];
arr[right] = temp;
/*此处是先排最大值的位置，所以得考虑最小值（arr[min]）在最大位置（right）的情况*/
if (min == right)
{ min = max; }
/*最小值放在最左端*/
temp = arr[min];
arr[min] = arr[left];
arr[left] = temp;
/*每趟遍历，元素总个数减少2，左右端各减少1，left和right索引分别向内移动1*/
left++;
right--;
}
选择排序的时间复杂度为O(n2)，空间复杂度O(1)
选择排序比冒泡排序要快，因为冒泡排序每趟比较过程中会交换多次，选择排序每趟只交换一次。
冒泡排序的交换在内循环中，选择排序的交换在外循环中
三、InsertSort
插入排序的思想是：
将初始数据分为有序部分和无序部分，每一步将一个无序部分的数据插入到前面已经排好序的有序部分中，直到插完所有元素为止。
插入排序的步骤：
每次从无序部分中取出一个元素，与有序部分中的元素从后向前依次进行比较，并找到合适的位置，将该元素插到有序组当中。
时间复杂度：最坏情况下为O(n2)，此时待排序列为逆序，或者说接近逆序
最好情况下为O(n)，此时待排序列为升序，或者说接近升序。
空间复杂度：O(1)
- 直接插入
// 插入排序 （直接插入）（交换）
public static void insertSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
for (int j = i - 1; j >= 0; j--) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
System.out.println(Arrays.toString(arr));
} else
break;
}
}
System.out.println(Arrays.toString(arr));
}
//这种插入方式是将某个位置的数和其前面一个进行比较，若该数比较小，则交换，直到比较
//交换到第0个数。
优化（移位）
// 优化：将某个位置的数与前面依次只比较不交换，直到确定最后的位置才进行交换。（移位）
public static void insertSort2(int[] arr) {
for (int i = 1; i < arr.length; i++) {
// 定义待插入的数
int insertVal = arr[i];
// arr[i] 前面的数的下标
int insertIndex = i - 1;
while(insertIndex >= 0 && insertVal < arr[insertIndex]) {
arr[insertIndex + 1] = arr[insertIndex];
insertIndex--;
}
// 判断是否需要赋值
if( insertIndex + 1 != i) {
arr[insertIndex + 1] = insertVal;
}
System.out.println("第"+i+"轮插入");
System.out.println(Arrays.toString(arr));
}
}
//或
public static void sort(int[] array){
for(int i = 1; i < array.length; i++){
int insertValue = array[i];
int j = i - 1;
//从右向左比较元素的同时，进行元素复制
for(; j >= 0 && insertValue < array[j]; j--){
array[j+1] = array[j];
}
//insertValue的值插入适当位置
array[j+1] = insertValue;
}
}
优化（折半插入排序）
在查找插入位置过程中引入折半查找算法思想，利用折半查找法在有序集中确定待排序元素插入位置。
public static void binarySort(int[] arr) { 1 2 4 5 3
// 循环遍历数组,定第2个元素开始,只有1个元素的话不用排序
for (int i = 1; i < arr.length; i++) {
int value = arr[i];
int low = 0;
int mid = 0;
int high = i - 1;
// 2分法查找要插入的位置,终止条件是high=mid-1以后比low小.
// 小于符号的满足条件的情况是high=low+1,mid=low,high=mid-1<low
while (low <= high) {
mid = (low + high) / 2;
// 如果比mid大,下次查找的数组为mid的后半段
if (value > arr[mid]) {
low = mid + 1;
// 否则下次查找的数组为mid的前半段
} else {
high = mid - 1;
}
}
// value就应该放到low这个位置,所以把low之后的元素都向后移动一格
for (int j = i; j > low; j--) {
arr[j] = arr[j - 1];
}
arr[low] = value;
}
}