选择 _ 冒泡 _ 快速 _ 插入
选择排序
思路
- 先从未排序的序列中选择最大（小）的元素，放到序列的起始位置。
- 在从余下的序列中依次选择元素放到以完成排序的元素末尾。
- 寻找最大（小）的元素需要遍历一次数组。for(int i = 0; i < arr.length; i++) {}。
- 在寻找余下的元素，依然需要再次遍历余下的数组，只不过此时的开始位置发生了变化。for(int j = i+1; j < arr.lengyh; j++) {}。
- 整体的思路也就是嵌套遍历两次数组。
代码
// 寻找最小元素
public int[] selSort01(int[] arr) {
// 遍历数组
for (int i = 0; i < arr.length; i++) {
// 从第二个数组开始寻找数组中余下数组中最小的那个元素
for (int j = i+1; j < arr.length; j++) {
// 满足条件后完成元素的交换
if (i < j && arr[i] > arr[j]) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
}
return arr;
}优化思路
上面的方法就是一个简单的选择排序。但它存在一个可以优化的问题。
- 在寻找最小元素的时候，如果我有两个元素比数组上的第一个元素要小，那么我要交换两次元素。
- 能不能直接找到对应的最小的那个元素，完成一次交换？
修改后的代码
public int[] selSort02(int[] arr) {
// 遍历数组
for (int i = 0; i < arr.length; i++) {
// 默认第一个数据元素为最小值
int min = i;
// 从第二个数值开始，找到余下数组中最小的那个元素
for (int j = i+1; j < arr.length; j++) {
if (i < j && arr[i] > arr[j]) {
min = j;
}
}
// 找到最小的那个元素，把它放到合适的位置
if(i != min) {
int tmp = arr[i];
arr[i] = arr[min];
arr[min] = tmp;
}
}
return arr;
}冒泡排序
思路
- 第一位的元素和第二位的元素比较，如果第一位的元素大于第二位的元素，那么两个元素互换位置。
- 当所有元素都交换一遍后，排序结束。
代码
public int[] maoPao01(int[] arr) {
for(int i = 0; i < arr.length; i++) {
for (int j = i+1; j < arr.length; j++) {
if(arr[j] > arr[j+1]) {
int tmp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tmp;
}
}
}
return arr;
}优化思路
这样写整体思路是对的，但如果去运行就会发现会报错。
原因如下：
- 第一个元素其实是不和自身去比较的，因此i < arr.length-1。同理 j < arr.lengt-1。
- 排序的操作其实是在第二个循环之中的，也就是 j 的操作中，但这个位置的元素是从首位开始的，因此 j = 0。
- 完成第一轮的排序后，在排序的时候，之前已经排好的元素是不参加比较的，因此 j < arr.length-1-i。这个时候 i 的作用也就体现出来了，它其实是控制排序次数的。
修改后的代码
public int[] maoPao01(int[] arr) {
// 认真思考会发现，如果元素有五个，那么其实排序的次数应该是4次。
// 因此 i < arr.length-1。
// 排序其实都是在第二个 for 循环里进行的，那么 j 的首位置应该是 0。
// 如果第一次排序完成，那么第二次排序其实是不需要在排第一次排序后的元素的，如何控制这个位置，其实就是第一个 for 循环起到的作用。
for(int i = 0; i < arr.length-1; i++) {
for (int j = 0; j < arr.length-1-i; j++) {
if(arr[j] > arr[j+1]) {
int tmp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tmp;
}
}
}
return arr;
}快速排序
思路
- 在数组中找一个支点，经过一趟排序后，支点左边的数都比支点小，支点右边的数都比支点大。
- 整体思路分为两步：第一步寻找这个支点，这个支点可以任意。第二步完成第一步的排序。
- 排序过程如下：
- 假定支点为最左边的元素：int tmp = arr[left]。
- 从数组的最右边开始，寻找比支点位置元素小的元素位置，然后停下（j–）。
- 从数组的最左边开始，寻找比支点位置元素大的元素位置，然后停下（i++）。
- 交换两元素的位置（`int temp = a[i]; a[i] = a[j]; a[j] = temp;）。
- 重复上述操作，直到 i 和 j 的位置重叠（i==j）。
- 交换支点位置上的元素和 i 所指示位置上的元素（a[left] = a[i];a[i] = pviot;）。
- 上述操作完成，此时：支点左边的元素都比支点小，支点右边的数据元素都比支点大。
- 然后对左边的元素进行上述同样的操作，对右边的元素进行上述同样的操作。
- 分析上述操作，可以发现，无论是排左边的元素还是右边的元素，都是在重复之前的操作，这个时候根据递归中整体和部分的关系，这一块的操作，可以借用递归来实现。
- 而递归的出口，就是当 i==j 的时候，当满足这个条件时，交换对应元素位置后，排序完成。
代码
public void querSort01(int[] arr,int k, int m) {
int left = 0;
int right = arr.length-1;
for (int i = 1; i < arr.length; i++) {
while (arr[i] > arr[left]) {
k = i;
}
}
for (int j = arr.length-1; j > 0; j--) {
while (arr[j] < arr[right]) {
m = j;
}
}
if (k == m){
int tmp = arr[left];
arr[left] = arr[k];
arr[k] = tmp;
}
}优化思路
上面的代码写道最后会发现，无法使用递归了。
整体思路没问题，但会发现当满足右边的数据比支点数据小，左边的数据比支点的数据大时，无法在交换数据元素。
遍历数组元素的时候，当满足一定条件的时候关键字 while 也是可以做到的。
修改后的代码
public void querSort02(int arr[], int left, int right) {
// 使用递归，就要有递归结束的条件
if (left >= right) {
return;
}
// 支点数据在代码后续容易改变，采用临时变量存储最为方便
int tmp = arr[left];
// 采用两个临时变量，代替元素移动
int i = left;
int j = right;
// 所有的操作都必须满足这个基本条件
while (i < j) {
// 从右边开始。寻找比支点小的元素
while (tmp <= arr[j] && i < j) {
j--;
}
// 从左边开始，寻找比支点大的元素
while (tmp >= arr[i] && i < j) {
i++;
}
// 找到对应元素后，交换彼此的位置
int point = arr[i];
arr[i] = arr[j];
arr[j] = point;
}
// 上述的操作都是在 （i < j） 这个条件下进行的。
// 在这个方法中，i 和 j 的关系只有 （i < j） 或者 （i == j）。
// 那么以下的操作就默认了是在（i == j） 的条件下进行的。
arr[left] = arr[i];
arr[i] = tmp;
// 上述完成第一轮的排序，接下来调用递归即可。
querSort02(arr, left, i - 1);
querSort02(arr, i + 1, right);
}插入排序
思路
- 默认待排序的数组第一个元素是有序的，把第二个元素到最后一个元素当作未排序的序列。
- 依次比较未排序的数组元素与第一个元素的大小关系，如果比第一个元素小，则交换位置。
代码
public int[] inSort01(int[] arr) {
// 因为第一个元素默认有序，所以这里从第二个位置开始
for (int i = 1; i < arr.length; i++) {
// 这里这样写有一个问题，那就是当前两个排序完成后，第三个数据元素不会在与第一个数据元素比较。
while(arr[i-1] > arr[i]) {
int tmp = arr[i];
arr[i] = arr[i-1];
arr[i-1] = tmp;
}
}
return arr;
}优化思路
上面的代码有一个问题，那就是：第三个数据元素不会与第一个数据元素进行比较，只会比较相邻位置的两个数据元素。
如果要解决上述的问题，就需要在引入一个变量，在相邻的位置的数据元素交换位置后，自动相减，以完成和初始位置上的元素进行比较。
因此可以引入变量 j 。在初始的时候，使它的值和 i 相等，完成一次比较的时候，在自动相减，这样 i 的值控制自增，j 的值控制自减。
另外就是完成某一动作的重复操作的时候，使用关键字 While 。
修改后的代码
public int[] inSort02 (int[] arr) {
// 因为第一个元素默认有序，所以这里从第二个位置开始
for (int i = 1; i < arr.length; i++) {
// 定义 j 变量，负责控制自减。
int j = i;
int tmp = arr[j];
// 当满足上一位已经排序好的元素比下一位元素的值大的时候，开始交换。
while(j > 0 && arr[j-1] > tmp) {
arr[j] = arr[j-1];
// 完成上面操作后 arr[j-1] 这个位置上是没有值的。
// j-- 在进入循环条件的时候，arr[j] 这个位置的元素是空的，元素的值在 tmp 那里。所以条件之中 arr[j-1] > tmp。
j--;
}
// 当这两个值不再相等的时候，完成下一步的交换。注意这个是 j 的值和一开始赋值给 j 的值是不同的。
if(i != j) {
arr[j] = tmp;
}
}
return arr;
}