常用算法-排序
涉及到算法的问题，如果针对是数组，大多数的情况下采用数组的下标。
1.1冒泡排序
思路：相邻的两个数进行比较，会进行n-1轮比较，每一轮会比较n-1次之后，将数组中最大的数排在最后。
注意：每一次比较之后, 条件成立则会交换变量值
packageday06;
importjava.lang.reflect.Array;
importjava.util.Arrays;
publicclassSort1 {
publicstaticvoidmain(String[] args) {
// 冒泡排序
int[] ns= {5, 8, 4, 2, 1, 6, 3};
// i ->轮数
for (inti=0; i<ns.length-1; i++) {
for (intj=0; j<ns.length-1-i; j++) {
// j -> 相邻的两个数据的比较
// 如果最大的放在最右边的话，前面的数大于后面的数则交换
// 如果最大的放在最右边的话，前面的数小于后面的数则交换
if( ns[j] <ns[j+1]){
ns[j] =ns[j] ^ns[j+1];
ns[j+1] =ns[j] ^ns[j+1];
ns[j] =ns[j] ^ns[j+1];
}
}
}
System.out.println(Arrays.toString(ns));
}
}
1.2快速排序
思路：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
实现的过程 ：
初始化 i=0, j=数组长度-1， k=数组名[i] 第一个数做为关键数（字）
首先： 因为i位置空出， 让j向左查到比k值小的，将值填充到i位置， i++
其次， 因为j位置空出， 让i向右查到比k值大的， 将值填充到j位置
最后，依次循环，直到i和j相遇时结束， 将k值放在i或j位置（相遇的位置）
本次结束之后， 确认了 k左边的所有数据比k小， 它的右边的数大k, 将左和右边分别按上面的排序方式 ，拆分进行排序。
packageday06;
importjava.util.Arrays;
publicclassSort2 {
staticvoidquicksort(int[] arr, intstart, intend){
// 待排序的数组元素只存在一个的情况下
if(start>=end) return;
inti=start, j=end, k=arr[i];
while (i<j){
// 1）依据j从右向左找一个比k的数，填充到 i位置
while (i<j&&arr[j] >=k) j--;
// 从j的位置 找到了比k小的数
if(i<j ){
// 将j的位置上的值填充到i
arr[i] =arr[j];
i++;
}
// 2） 依据i 从左向右找到一个比k大的数，填充到 j位置
while (i<j&&arr[i] <=k) i++;
if (i<j){
arr[j] =arr[i];
j--;
}
}
// i 和 j 相遇了
arr[i] =k; // 最主要是找出关键数应该放的位置
quicksort(arr, 0, i-1); // 关键数的左边
quicksort(arr, i+1, end); // 关键数的右边
}
publicstaticvoidmain(String[] args) {
int[] ns= {3, 2, 9, 5, 1, 6, 7};
quicksort(ns, 0, ns.length-1);
System.out.println(Arrays.toString(ns));
}
}
1.3插入排序
思路：从数组的第一个元素a[0]开始，将其后一个元素a[1]插入到a[0]的前面或者后面，接着继续这一过程。 【注意】每次都是将a[i]插入到已经排序好的a[0]~a[i-1]中合适的位置
packageday06;
importjava.util.Arrays;
publicclassInsertSort3 {
publicstaticvoidmain(String[] args) {
int[] ns= {5, 2, 1, 4, 6, 3, 7};
// 初始情况下：认为a[0] 是有序的
// 到 i位置，认为 a[0] ~ a[i-1] 区间是有序
// 算法：将 i位置的数，插入到a[0] ~ a[i-1]有序区间的合适位置
for (inti=1; i<ns.length; i++) {
// 从当前的i位置向左边找到这个数合适的位置
for (intj=i; j>0; j--) {
// 从小到大： 当前位置 小于 前一个数则交换
// 从大到小: 当前位置 大于 前一个数则交换
if(ns[j] <ns[j-1]){
ns[j] =ns[j] ^ns[j-1];
ns[j-1] =ns[j] ^ns[j-1];
ns[j] =ns[j] ^ns[j-1];
}elsebreak; // 优化的算法
}
}
System.out.println(Arrays.toString(ns));
}
}
与选择排序比较
①二者平均时间复杂度都是O(n^2)；
②大部分情况下，插入都略优于选择；
③有序集合插入的时间复杂度为O(n)；
④插入属于稳定排序算法，而选择属于不稳定排序