1. 简单排序
- 基本思想
每次选出最小的数放入合适的位置，也就是说对于一个待排序数组，首先从0-n-1下标中选出最小的放在0位置上，再从1-n-1中选出最小的放入到1位置上，依此类推直到最后只剩下最后一个待选择元素，说明排序完毕。 - 时间复杂度和空间复杂度
由于选择排序和数况没关系，第一次要从n个元素中选出最小的，第二次要从n-1个元素中选出最小的，第三次…将上述操作看作常数操作，那么总操作数为：N+N-1+N-2+…,可知是一个等差数列，那么时间复杂度为O(n²)
由于没有额外开数组，所以空间复杂度为O(1). - 代码实现
//选择排序
public static void SelectedSort(int arr[]){
for (int i = 0; i < arr.length; i++) {
int midIndex = i;
for (int j = i+1; j < arr.length; j++) { //这个for每次得到最小值的下标
midIndex = arr[midIndex]>arr[j] ? j : midIndex;
}
if(i!=midIndex)
swap(arr,i,midIndex);
}
Show(arr);
}
2. 冒泡排序
- 基本思想
对于一个待排序的数组，每次两两比较，即0与1，1与2，2与3…如果后面的小于前面的，则两两交换，比较到n-1位置说明一趟结束，此时n-1位置上的数不用动了，因为已经有序。下次从比较到n-2结束，n-2位置有序，若有一趟没有任何交换或者已经比较n-1趟说明排序完毕。 - 时间复杂度和空间复杂度
冒泡排序也和数况没有关系，比较次数每次都是固定的，第一次两两比较n-1次，第二次n-2次，依此类推，计算常数操作次数，和选择排序一样为n-1+n-2+…是一个等差数列，所以时间复杂度同样是O(n²).空间复杂度也为O(1) - 代码实现
//冒泡排序
public static void BubbleSort(int arr[]){
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length-i-1; j++) {
if(arr[j+1]<arr[j]){ //两两比较
swap(arr,j,j+1);
}
}
}
Show(arr);
}
3. 插入排序
- 基本思想
插入排序是遵循一个有序的思想，对于一个待排序的数组，认为第一个(下标为0）元素是有序的，其他n-1个元素视为无序。首先将无序元素中的第一个元素插入到有序列表中，第一次有序表只有一个元素，所以与之比较，小于这个元素则交换，自此有序表有2个元素，再拿无序表中第一个元素，与有序表中的元素从右至左比较，小于当前元素则交换，直至前面没有比它大的或者已经到了第0个位置则插入成功。依次类推，直至无序列表为空，此时数组有序。 - 时间复杂度和空间复杂度
插入排序与上面两种排序不同，排序效率受数况的影响。对于一个逆序的数组，插入排序每次插入元素都会比较最多次数，例如第一次比较一次交换一次，第二次比较两次交换两次，第n-1次比较n-1次交换n-1次，常数操作数是等差数列，为O(n²)。对于一个已经有序的数组，每次都只需要比较一次不需要交换，次数为常数次，复杂度为O(n).由于一般考虑最坏时间复杂度，所以插入排序为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&&arr[j+1]<arr[j]; j--) { //与有序表从右至左依次比较
swap(arr,j,j+1);
}
}
Show(arr);
}
4. 关于位运算
首先说说上述排序中的swap函数
一般写法是：
public static void swap(int arr[],int i,int j){
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
借助位运算：
//注意使用位运算时，应避免i和j相等，不然最后异或结果都为0，达不到交换的目的
public static void swap(int arr[],int i,int j){
arr[i] = arr[i]^arr[j]; (1)
arr[j] = arr[i]^arr[j]; (2)
arr[i] = arr[i]^arr[j]; (3)
}
通常位运算是比数字运算快很多的。所以能采取位运算尽量采取位运算。
位运算原理：
位运算有一个性质为两个位异或，相同为0相异为1，还有一个性质是自己和自己异或为0和任何数与0异或等于本身,且满足交换律和结合律。
这里简单说明一下上述swap原理
假设arr[i]=a,arr[j]=b.由(1)得：arr[i]=a ^ b,arr[j]=b;
由(2)得：arr[i]=a ^ b, arr[j]=a ^ b ^b=a ^ 0=a
由(3)得：arr[i]=a ^ b ^ a = b ^ 0 = b，a[j]=a
这样就达到了交换的目的。
5.位运算扩展（位运算能解决的问题）
1.有这样一组数，相邻两个数不等，其中某个数出现了奇数次，其他数均出现了偶数次，求这个奇数是什么？
方案：通过位运算，声明一个变量x=0，让x与这组数从头异或到尾，那么最终异或结果就是这个奇数。
原理：因为异或具有结合律和交换律，所以这组数中的偶数次数相互结合异或得0，而x也是0，最后就会单一个奇数出来（奇数个拿出来偶数个），即为所求。
2.再有这样一组数，相邻两个数不等，其中某两个数出现了奇数次，其他数出现了偶数次，求出现奇数次的两个数是什么？
方案：还是先声明一个变量x=0，同样与这组数进行异或，那么最后就会得到x=a ^ b,由于a肯定不等于b（两个数），所以x=a^b 肯定不为0，那么a和b异或肯定有一位不为0，也即a和b的那一位是相异的，a为1，b就为0，反之亦然。假设a和b第6位不相同，那这组数也可以分为两类，一类是与a一样，一类是与b一样。再声明一个变量y=0，将y与这组数中的其中一类进行异或，那么会单出来a或者b（那些偶数次的数还是没有影响），即y=a or y=b，最后将y与x异或就得到a或者b，如果x ^ y=a，那么y=b，反之亦然，x ^ y和y即为所求的两个奇数。
代码实现：
public static void bit(int arr[]){
int x = 0;
for(int e:arr){
x ^= e;
}
int rightOne = x & (~x+1);//取出最右边的1
int y = 0;
for(int e: arr){
if(rightOne & e == 1) //将y与某一类进行异或，这里等于1或者0均可
{
y ^= e;
}
}
System.out.println("第一个奇数："+y,"第二个奇数："+y ^ x)
}
6. 对数器
对数器实际上是自测自己写的算法的一个正确与否的一个好方法,可以不依赖于oj。以上述三个手写的排序函数为例，来对三个排序函数进行测试。
public static void logForTest(){ //测试方法
int times = 10000；//测试一万组
boolean f = false;
for (int i = 0; i < times; i++) {
int arr[] = returnRandomArr();
int arr1[] = Arrays.copyOf(arr,arr.length);
int arr2[] = Arrays.copyOf(arr,arr.length);
SelectedSort(arr);//选择排序
BubbleSort(arr1);//冒泡排序
InsertSort(arr2);//插入排序
Arrays.sort(arr3);//系统方法用于对照
Show(arr3);
for (int j = 0; j < arr.length; j++) {
if(arr[i]!=arr1[i] || arr[i]!=arr2[i] || arr1[i]!=arr2[i]||
arr[i]!=arr3[i]||arr1[i]!=arr3[i]||arr2[i]!=arr3[i]){
f = true;
break;
}
}
if(f) System.out.println("失败");
else System.out.println("成功");
}
}
public static int[] returnRandomArr(){//随机生成测试用例
Random random = new Random();
int maxValue = random.nextInt(100);
int arr[] = new int[random.nextInt(100)];
for (int i = 0; i < arr.length; i++) {
arr[i] = random.nextInt(maxValue+1)-random.nextInt(maxValue);
}
Show(arr);
return arr;
}
三个排序算法测试结果：
初始数组：17 4 -60 -42 14 30 58 52 52 34 -6 4 55 34 0 21 -30 21 -18 -26 -13 26 20 70 8 -2 -5 -24 -19 -39 -45 -16 37 71 -7 -29 -13 49 -21 -27 -66 61 -29 -48 35 -34 37 -20 18 -51 62 31
选择排序：-66 -60 -51 -48 -45 -42 -39 -34 -30 -29 -29 -27 -26 -24 -21 -20 -19 -18 -16 -13 -13 -7 -6 -5 -2 0 4 4 8 14 17 18 20 21 21 26 30 31 34 34 35 37 37 49 52 52 55 58 61 62 70 71
冒泡排序：-66 -60 -51 -48 -45 -42 -39 -34 -30 -29 -29 -27 -26 -24 -21 -20 -19 -18 -16 -13 -13 -7 -6 -5 -2 0 4 4 8 14 17 18 20 21 21 26 30 31 34 34 35 37 37 49 52 52 55 58 61 62 70 71
插入排序：-66 -60 -51 -48 -45 -42 -39 -34 -30 -29 -29 -27 -26 -24 -21 -20 -19 -18 -16 -13 -13 -7 -6 -5 -2 0 4 4 8 14 17 18 20 21 21 26 30 31 34 34 35 37 37 49 52 52 55 58 61 62 70 71
系统方法：-66 -60 -51 -48 -45 -42 -39 -34 -30 -29 -29 -27 -26 -24 -21 -20 -19 -18 -16 -13 -13 -7 -6 -5 -2 0 4 4 8 14 17 18 20 21 21 26 30 31 34 34 35 37 37 49 52 52 55 58 61 62 70 71
result：成功
-2 44 -46 9 16 -65 29 -57 -3 -27 41 -74 -44
-74 -65 -57 -46 -44 -27 -3 -2 9 16 29 41 44
-74 -65 -57 -46 -44 -27 -3 -2 9 16 29 41 44
-74 -65 -57 -46 -44 -27 -3 -2 9 16 29 41 44
-74 -65 -57 -46 -44 -27 -3 -2 9 16 29 41 44
成功
-25 -15 20 -2 -15 -28 8 8 20 7 2 -4 12 -9 15 -8 13 14 -23 -17 -19 3 -25 -42 4 -13 22 22 4 -11 -32 -3 24 19 14 8 -26 25 2 13 -35 -3 2 30 -6 1 -10 8 -11 23 -22 -8 17 6 -20 12 2 -11 -12 -7 -3 12 34 20 -4 8 14
-42 -35 -32 -28 -26 -25 -25 -23 -22 -20 -19 -17 -15 -15 -13 -12 -11 -11 -11 -10 -9 -8 -8 -7 -6 -4 -4 -3 -3 -3 -2 1 2 2 2 2 3 4 4 6 7 8 8 8 8 8 12 12 12 13 13 14 14 14 15 17 19 20 20 20 22 22 23 24 25 30 34
-42 -35 -32 -28 -26 -25 -25 -23 -22 -20 -19 -17 -15 -15 -13 -12 -11 -11 -11 -10 -9 -8 -8 -7 -6 -4 -4 -3 -3 -3 -2 1 2 2 2 2 3 4 4 6 7 8 8 8 8 8 12 12 12 13 13 14 14 14 15 17 19 20 20 20 22 22 23 24 25 30 34
-42 -35 -32 -28 -26 -25 -25 -23 -22 -20 -19 -17 -15 -15 -13 -12 -11 -11 -11 -10 -9 -8 -8 -7 -6 -4 -4 -3 -3 -3 -2 1 2 2 2 2 3 4 4 6 7 8 8 8 8 8 12 12 12 13 13 14 14 14 15 17 19 20 20 20 22 22 23 24 25 30 34
-42 -35 -32 -28 -26 -25 -25 -23 -22 -20 -19 -17 -15 -15 -13 -12 -11 -11 -11 -10 -9 -8 -8 -7 -6 -4 -4 -3 -3 -3 -2 1 2 2 2 2 3 4 4 6 7 8 8 8 8 8 12 12 12 13 13 14 14 14 15 17 19 20 20 20 22 22 23 24 25 30 34
成功
-2 -8 5 -12 -10 -6 -3 0 4 9 -5 2 2 3 9 -6 -8 -1 -5 0 11 6 -15 6 -9 -9 10 -7 5 6 9 2 -4 2 0 11 6 10 -2 4 -13 9 -11 -2 2 -4 6 1 0 5 3 0 -6 4 0 -11
-15 -13 -12 -11 -11 -10 -9 -9 -8 -8 -7 -6 -6 -6 -5 -5 -4 -4 -3 -2 -2 -2 -1 0 0 0 0 0 0 1 2 2 2 2 2 3 3 4 4 4 5 5 5 6 6 6 6 6 9 9 9 9 10 10 11 11
-15 -13 -12 -11 -11 -10 -9 -9 -8 -8 -7 -6 -6 -6 -5 -5 -4 -4 -3 -2 -2 -2 -1 0 0 0 0 0 0 1 2 2 2 2 2 3 3 4 4 4 5 5 5 6 6 6 6 6 9 9 9 9 10 10 11 11
-15 -13 -12 -11 -11 -10 -9 -9 -8 -8 -7 -6 -6 -6 -5 -5 -4 -4 -3 -2 -2 -2 -1 0 0 0 0 0 0 1 2 2 2 2 2 3 3 4 4 4 5 5 5 6 6 6 6 6 9 9 9 9 10 10 11 11
-15 -13 -12 -11 -11 -10 -9 -9 -8 -8 -7 -6 -6 -6 -5 -5 -4 -4 -3 -2 -2 -2 -1 0 0 0 0 0 0 1 2 2 2 2 2 3 3 4 4 4 5 5 5 6 6 6 6 6 9 9 9 9 10 10 11 11
成功
3 3 6 1 4 3 2 4 1 -5 0 5 2 -8 1 -3 4 6 5 -2 -3 -4 1 -3 2 -3 3 -3 -5 2 0 6 2 -6 -3 8 2 6 -3 7 0 -3 3 0 4 -3 7 -3 -3 0 -5 1 2 1 6 2 -6 -2 5 -7 -1 0 -8 3 4 -3 2
-8 -8 -7 -6 -6 -5 -5 -5 -4 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -2 -2 -1 0 0 0 0 0 0 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 4 4 4 4 4 5 5 5 6 6 6 6 6 7 7 8
-8 -8 -7 -6 -6 -5 -5 -5 -4 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -2 -2 -1 0 0 0 0 0 0 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 4 4 4 4 4 5 5 5 6 6 6 6 6 7 7 8
-8 -8 -7 -6 -6 -5 -5 -5 -4 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -2 -2 -1 0 0 0 0 0 0 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 4 4 4 4 4 5 5 5 6 6 6 6 6 7 7 8
-8 -8 -7 -6 -6 -5 -5 -5 -4 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -2 -2 -1 0 0 0 0 0 0 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 4 4 4 4 4 5 5 5 6 6 6 6 6 7 7 8
成功
-66 7 -6 16 -45 -38 -20 52 -32 16 -1 -26 -17 59 -18 70 -21 -33 -29 7 -19 -5 -22 -10 -46 17 9 -55 -22 -15 25 -41 17 14 -23 -49 -55 3 25 -16 34 -2
-66 -55 -55 -49 -46 -45 -41 -38 -33 -32 -29 -26 -23 -22 -22 -21 -20 -19 -18 -17 -16 -15 -10 -6 -5 -2 -1 3 7 7 9 14 16 16 17 17 25 25 34 52 59 70
-66 -55 -55 -49 -46 -45 -41 -38 -33 -32 -29 -26 -23 -22 -22 -21 -20 -19 -18 -17 -16 -15 -10 -6 -5 -2 -1 3 7 7 9 14 16 16 17 17 25 25 34 52 59 70
-66 -55 -55 -49 -46 -45 -41 -38 -33 -32 -29 -26 -23 -22 -22 -21 -20 -19 -18 -17 -16 -15 -10 -6 -5 -2 -1 3 7 7 9 14 16 16 17 17 25 25 34 52 59 70
-66 -55 -55 -49 -46 -45 -41 -38 -33 -32 -29 -26 -23 -22 -22 -21 -20 -19 -18 -17 -16 -15 -10 -6 -5 -2 -1 3 7 7 9 14 16 16 17 17 25 25 34 52 59 70
成功
···