目录

swap交换方式 

位运算

数学计算

通过数组交换

冒泡排序

冒泡排序的基本思想

代码设计

代码实现

时间、空间复杂度

选择排序

选择排序的基本思想

代码设计

代码实现

时间、空间复杂度

插入排序

插入排序的基本思想

代码设计

代码实现

时间、空间复杂度

位运算主要针对整型，数学计算主要针对小数和整型，数组最为常用。

1. 位运算，两数字异或处理
2. 数学计算
3. 通过数组交换

位运算

异或  ^

将数字转化为二进制形式，对应的两个数字（0 / 1）相同，结果为0，若不同，结果为0.

a = a^b	0100 0011 0111	a=7(0111)
b = a^b	0111 0011 0100	b = 4
a = a^b	0111 0100 0011	a = 5

private static  void  swap3 (int[] element,int index1,int index2){
        element[index1] = element[index1]^element[index2];
        element[index2] = element[index1]^element[index2];
        element[index1] = element[index1]^element[index2];
    }

数学计算

 a: 4   b: 5

a = a + b    a = 9  b = 5

b = a - b    a = 9  b = 4

a = a - b    a = 5  b = 4

private static void swap2(int[] element,int index1,int index2){
        // 数学计算
        element[index1] = element[index1]+element[index2];
        element[index2] = element[index1]-element[index2];
        element[index1] = element[index1]-element[index2];
}

通过数组交换

定义中间变量 temp 交换即可。

 private static  void  swap1 (T[] element,int index1,int index2){
        T temp = element[index1];
        element[index1] = element[index2];
        element[index2] = temp;
    }

 不能这样写，形参影响不到实参，结果并没有交换。

 public static void swap(int a,int b){
        int temp = a;
        a = b;
        b = temp;
    }
    public static void main(String[] args) {
        int a = 3;
        int b = 5;
        swap(a,b);
        System.out.println("a:"+a+ " b:"+b);
    }

冒泡排序

冒泡排序是稳定的。

冒泡排序的基本思想

第一趟：使第1个数和第2个数进行比较，小的在前，大的在后；第2个数再和第3个数进行比较，小的在前，大的在后；依次比较到最后两个数即可。最后一个数即为所有数字中最大的。

第二趟：第1个数和第2个数进行比较，小的在前，大的在后；第2个数再和第3个数进行比较，小的在前，大的在后；依次比较到倒数第三和倒数第二个数即可；倒数第二个数便可得到。

······

第 n 趟：第一个数和第2个数进行比较；排序完成。

冒泡排序的优化：

定义一个boolean类型的变量flag，在外循环内，内循环外，若每完成依次内循环，则flag为true，否则为false，若内循环没有发生交换，则说明内部排序完成，则flag未发生改变，为false，则break，跳出外循环。

排序完成。

 

代码设计

用二重循环完成：外循环变量用 i 表示，内循环变量设为 j ，假设共有 n 个数，外循环 n-1 次，内循环 每趟为（n-1 、n-2、n-3、···、2、1）即为（elemnet.length - i -1）次。每两个比较的数与内循环j有关，表示为 element [j] 和 element [j+1]。

代码实现

public class bubbleSort {
    public static> void BubbleSort(T[] element){
        // 若数组为空或数组长度为1 ，则直接return
        if(element == null || element.length == 1){
            return;
        }
        for(int i = 0;i  0){   // 前者大于后者
                    swap1(element,j,j+1);
                    flag = true;
                }
            }
            if(!flag){
                break; // 退出循环
            }
        }
    }
private static  void  swap1 (T[] element,int index1,int index2){
        T temp = element[index1];
        element[index1] = element[index2];
        element[index2] = temp;
    }

 public static void main(String[] args) {
        Integer[] array = new Integer[]{1,4,5,7,2,3,6,8};
        BubbleSort(array);
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]+" ");
        }

    }
}

时间、空间复杂度

空间复杂度：O(1)    没有开辟新的内存空间

时间复杂度： O(N^2)    

最优时间复杂度： O(N)   ，当序列趋近与完全有序时。

有以下两种情况满足这个条件:

1. 3   4   5   7,遍历一遍后退出。遍历次数 n-1；
2. 4   3   5   7，第一遍遍历，前两个数交换，第二次遍历，完全有序，退出。(n-1)+(n-2) 

选择排序

选择排序是不稳定的。

选择排序的基本思想

序列分为有序序列和无序序列两部分。每次遍历无序的列表，当找到最小的，将最小的数字和无序序列的第一位交换，交换后的无序序列第一位即变为有序的序列。

•  初始状态下，序列是无序的，有序的序列为空。
• 第一遍遍历，找到最小的数字，与当前序列的第一位交换，第一位即归为有序序列。其后为无序序列
• 第二遍遍历，从第二位数字（即无序序列）开始遍历，找到最小的数字，与无序序列的第一位交换，前两个数字即为有序序列，其后为无序序列。
• ……
• ……
• ……
• 第n-1遍遍历，确定最后两个数字的大小

 

代码设计

使用双重循环完成，i 控制趟数，j 控制每次遍历比较的次数

定义最小值的下标 minIndex，初始 minIndex = i；当其后有数字小于minIndex时，minIndex 更新为 j （该较小数字的下标）

遍历完成后，交换下标为 i 和 minIndex的值。

代码实现

    public static> void selectSort(T[] element){
        if(element == null || element.length == 1){
            return;
        }
        for(int i=0;i< element.length;i++){
            int minIndex = i;
            for(int j = i; j< element.length;j++){
                if(element[j].compareTo(element[minIndex]) < 0){
                    minIndex = j;
                }
            }
            swap(element,minIndex,i);
        }
    }
    private static  void  swap (T[] element,int index1,int index2){
        T temp = element[index1];
        element[index1] = element[index2];
        element[index2] = temp;
    }

    public static void main(String[] args) {
        Integer[] arr = new Integer[]{1,4,6,3,2,7};
        selectSort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
    }

时间、空间复杂度

空间复杂度：O(1)    没有开辟新的内存空间

平均时间复杂度： O(N^2)    

最优时间复杂度： O(N^2)

插入排序

插入排序的基本思想

序列分为有序的和无序的。

初始状态下，序列的第一个数为有序的，无序序列的第一个值与有序序列的值从后向前比较，将该值有序的插入有序序列中，使得原来的有序序列成为长度加一的有序序列。

代码设计

定义 i 和 j ，i 控制 有序序列的最后一位元素，j = i + 1，j 则是无序序列的第一个值（即为待比较的值）。j (element [ j ] ) 和 前一个数 element [ j -1 ] 进行比较，若小于前一个元素，则 j --；继续比较，若大于前一个元素。停止比较。i++；有序序列长度加一。

若j的前一个元素   element [ j-1 ]  下标 j -1<0,则该元素与所有元素进行比较，为当前有序序列中最小的元素。i++;

代码实现

    public static> void insertSort(T[] element){
        if(element == null||element.length == 1){
            return;
        }
        for(int i = 0;i< element.length;i++){
            int j;
            if(i == element.length -1){
                j = i;
            }else{
                j = i+1;
            }
     
            for(;j>0;j--){
                if(element[j] .compareTo(element[j-1])<0){
                    swap(element,j,j-1);
                }else{
                    break;
                }
            }
        }
    }
    private static  void  swap (T[] element,int index1,int index2){
        T temp = element[index1];
        element[index1] = element[index2];
        element[index2] = temp;
    }
    public static void main(String[] args) {
        Integer[] arr = new Integer[]{1,4,6,3,2,7};
        insertSort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
    }

时间、空间复杂度

空间复杂度：O(1)    没有开辟新的内存空间

平均时间复杂度： O(N^2)    

最优时间复杂度： O(N)  当序列为有序序列时，例如  1 2 3 4 5