排序算法研究

cover

冒泡排序法(Bubble Sort)

冒泡排序(Bubble Sort)的基本思想是:通过对待排序序列从后向前(从下标较大的元素开始),依次比较相邻元素的排序码,若发现逆序则交换,使排序码较小的元素逐渐从后部移向前部(从下标较大的单元移向下标较小的单元),就象水底下的气泡一样逐渐向上冒。

因为排序的过程中,各元素不断接近自己的位置,如果一趟比较下来没有进行过交换,就说明序列有序,因此要在排序过程中设置一个标志flag判断元素是否进行过交换。从而减少不必要的比较。

class Bubble{
    public void sort(int [] arr) {

        int temp;   //创建一个临时变量用于交换数据
        //外层循环决定走几趟
        for (int i=0; i < arr.length-1; i++) {  //length-1是因为最后一个数字不必再做交换
            //内层循环比较前后两个数大小 若前一个数比后一个数大,则交换
            for (int j=0; j < arr.length-1-i; j++) { //length-1-i 是因为最大数交换至数组尾部 不必再参与比较 
                if (arr[j]>arr[j+1]) {
                    //若前一个大于后一个数,则交换
                    temp = arr[j];      
                    arr[j]=arr[j+1];
                    arr[j+1]=temp;
                }
            }
        }   
    }
}

选择排序法(Selection Sort)

选择排序(Selection Sort)也是一种简单的排序方法。它的基本思想是:第一次从R[0]-R[n-1]中选取最小值,与R[0]交换,第二次从R[1]-R[n-1]中选取最小值,与R[1]交换,第三次从R[2]-R[n-1]中选取最小值,与R[2]交换,...,第i次从R[i-1]-R[n-1]中选取最小值,与R[i-1]交换,...,第n-1次从R[n-2]-R[n-1]中选取最小值,与R[n-2]交换,总共通过n-1次,得到一个按排序码从小到大排列的有序序列。

例如,给定n=8,数组R中的8个元素的排序码为:(8,3,2,1,7,4,6,5),选择排序过程。

//选择排序法 Selection Sort
class Select{
    public void sort(int [] arr) {
        int temp;
        for (int i=0; i<arr.length-1;i++) {  //一共进行length-1轮比较
            int min =arr[i];    //先假设每轮第一个数是最小的
            int minIndex = i;   //记录最小数的下标
            //将这个数与后面的所有数字挨个比较 找出后面数中的最小值和其下标
            for (int j=i+1; j < arr.length; j++) { 
                                if (min>arr[j]) {
                         min = arr[j];
                         minIndex = j;
                }
            //将循环后的找到的最小值放与每轮第一个数字交换    
            temp = arr[i];
            arr[i] = arr[minIndex];
            arr[i+1]=temp;
            }
        }
    }
}

插入排序法(Insertion Sort)

插入排序(Insertion Sort)的基本思想是:把n个待排序的元素看成为一个有序表和一个无序表,开始有序表只包含一个元素,无序表中包含有n-1个元素,排序过程中每次从无序表中取出第一个元素,把它的排序码依次与有序表元素的排序码进行比较,将它插入到有序表中的适当位置,使之成为新的有序表。

//插入排序法 Insertion Sort
class Insert{
    public void sort(int []arr) {
        for (int i=1; i< arr.length; i++) { int insertVal = arr[i]; //需要的插入的数提取出来,准备和前面的数比较 int index = i-1; 
                             //index位需要插入的数前面的数的下标 
                        while (index >=0 && insertVal < arr[index]) {
                arr[index+1]= arr[index];   //将index那一位数字向后移动一个
                index--;    //index向前进一个,准备和再前面的数字比较
            }
            arr[index+1]= insertVal;    //insertVal插入到适当的位置
        }
    }
}

为TA充电
共{{data.count}}人
人已赞赏
服务器运维系统运维

使用SSL证书为Windows(非Server)远程桌面RDP连接加密

2018-4-11 12:34:52

服务器运维网站运维

巧用新浪图床API加速你的网站

2020-2-17 13:09:13

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
搜索