常见排序算法总结（java版）

一、冒泡排序

1、原理：相邻元素两两比较，大的往后放。第一次完毕，最大值在最大索引处。

即使用相邻的两个元素一次比价，依次将最大的数放到最后。

2、代码：

public static void bubbleSort(int[] arr) {
                    for(int x=0; x<arr.length-1; x++) {  //外层循环控制轮数 ,一共要比较（arr.length-1）轮
                        for(int y=0; y<arr.length-1-x; y++) {  //外层循环控制每一轮比较的次数,每一轮比较（arr.length-1-i）次
                            if(arr[y] > arr[y+1]) {      //如果前面的元素比后面的元素大，则交换位置
                                int temp = arr[y];
                                arr[y] = arr[y+1];
                                arr[y+1] = temp;
                            }
                        }
                    }
                }

View Code

二、选择排序

1、原理：将0位置的元素依次和后面全部的元素比，比完后，0位置就是最小的元素，紧接着从1位置对后面的元素比，逐步得到从小到大的值。

即用每一个元素，与其他元素一次比较，一次将最小的数放到最前面。

2、代码：

 public static void selectionSort(int[] arr){
        for(int i=0;i<arr.length;i++){   //外层循环控制用哪个位置的数与后面的数比较
            for (int j=i+1;j<arr.length;j++){ // 内层循环控制这个数与后面的数需要比较多少次
                if(arr[i]>arr[j]) { // //这个条件保证从小到大排列，反之从大到小排列
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }

View Code

三、快速排序

1、原理：

　　（1）先从数列中取出一个数作为key值

　　（2）将比这个数小的数全部放在它的左边，大于或等于它的数全部放在它的右边

　　（3）对左右两个小数列重复第二步，直至各区间只有1个数。

2、代码

public static void quickSort(int a[], int left, int right) {
        if (left >= right) {  //若果左边的指针大于右边的指针，直接跳出
            return;
        }

        int low = left; //定义左指针
        int high = right; //定义右指针
        int key = a[left];//选择第一个数为key

        while (low < high) {

            while (low < high && a[high] >= key)//从右向左找第一个小于key的值
                high--;
            if (low < high) {
                a[low] = a[high];
                low++;
            }

            while (low < high && a[low] < key)//从左向右找第一个大于key的值
                low++;

            if (low < high) {
                a[high] = a[low];
                high--;
            }
        }
        //当low == high时
        a[low] = key;
        quickSort(a, left, low - 1);//递归调用
        quickSort(a, low + 1, right);//递归调用
    }

View Code

参考链接：

（1）8大排序算法图文详解：

http://www.jianshu.com/p/e6ad4423efcd

（2）8大排序算法Python版：

http://www.jianshu.com/p/7d037c332a9d

（3）8大排序算法Java版：

http://www.jianshu.com/p/ae97c3ceea8d