By

Contents
  1. 1. 冒泡排序(三种实现)
  2. 2. 快速排序

交换排序分为 冒泡排序 和 快速排序

冒泡排序(三种实现)

冒泡排序是非常容易理解和实现，以从小到大排序举例：
顾名思义，就是排序时，最大的元素会如同气泡一样移至右端，其利用比较相邻元素的方法，将大的元素交换至右端，
所以大的元素会不断的往右移动，直到适当的位置为止。
基本的气泡排序法可以利用旗标的方式稍微减少一些比较的时间，当寻访完阵列后都没有发生任何的交换动作，
表示排序已经完成，而无需再进行之后的回圈比较与交换动作。

设数组长度为N。

  • 1．比较相邻的前后二个数据，如果前面数据大于后面的数据，就将二个数据交换。

  • 2．这样对数组的第0个数据到N-1个数据进行一次遍历后，最大的一个数据就
    “沉”到数组第N-1个位置。

  • 3．N=N-1，如果N不为0就重复前面二步，否则排序完成。

  • 按照定义写

public static void bubbleSort(int[] a) {
    int temp = 0;
    for (int i = 0; i < a.length - 1; i++) {
        for (int j = 0; j < a.length - 1 - i; j++) {
            if (a[j] > a[j + 1]) {
                temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
            }
        }
    }
    printSort(a);
}
  • 改进 增加一个标志flag 如果有一趟没有发生交换，排序完成
public static void bubbleSort1 (int[] data){
    int len = data.length;
    boolean flag =true;
    while(flag){
        flag =false;
        for (int i=1;i<len;i++){
            if (data[i-1] > data[i]) {
                swap(data, i-1, i);
                flag =true;
            }
        }
        len--;
    }    
}
  • 改进 假设在某一位后是有序的怎么办 没有必要再每次都比较后面的
public static void bubbleSort2(int[] data){
    int len=data.length;
    int flag =len;
    while(flag >0){
        int k=flag;
        flag =0;
        for(int i=1;i<k;i++){
            if (data[i-1]>data[i]) {
                swap(data, i-1, i);
                flag = i;
            }
        }
    }
}

冒泡排序毕竟是一种效率低下的排序方法，在数据规模很小时，可以采用。数据
规模比较大时，最好用其它排序方法。

快速排序

快速排序是 C.R.A.Hoare 于 1962 年提出的一种划分交换排序。它采用了一种分
治的策略，通常称其为分治法(Divide-and-ConquerMethod)。
基本思想
1．先从数列中取出一个数作为基准数。
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它
的左边。
3．再对左右区间重复第二步，直到各区间只有一个数。
虽然快速排序称为分治法，但分治法这三个字显然无法很好的概括快速排序的全
部步骤。因此我的对快速排序作了进一步的说明： 挖坑填数+分治法

public static void quickSort1(int[] data, int left, int right) {
    if (left < right) {
        int x = data[left];  //习惯性将第一个数给挖坑了
        int i = left, j = right;   
        while (i < j) {
            while (i < j && data[j] > x) //从左向右找比这个坑里面大的
                j--;
            data[i] = data[j];    //挖坑填平
            while (i < j && data[i] < x) //从右向左找比这个坑小的
                i++;
            data[j] = data[i]; //遇到大的就挖坑把原来的填平
        }
        data[i] = x;  最后把原来的坑里面的数放到最后一个坑里
        quickSort1(data, left,  i - 1);
        quickSort1(data, i + 1, right);
    }
}
Contents
  1. 1. 冒泡排序(三种实现)
  2. 2. 快速排序