一、冒泡排序
冒泡排序是简单的排序之一了，其大体思想就是通过与相邻元素的比较和交换来把小的数交换到前面。这个过程类似于水泡向上升一样，因此而得名。
举个例子，对5,3,8,6,4这个无序序列进行冒泡排序。首先从后向前冒泡，4和6比较，把4交换到前面，序列变成5,3,8,4,6。
同理4和8交换，变成5,3,4,8,6,3和4无需交换。5和3交换，变成3,5,4,8,6,3.这样一次冒泡就完了，把小的数3排到前面了。
对剩下的序列依次冒泡就会得到一个有序序列。冒泡排序的时间复杂度为O(n^2)。
public class SelectSort {
public static void selectSort(int[] arr) {
if(arr == null || arr.length == 0)
return ;
int minIndex = 0;
for(int i=0; i minIndex = i;
for(int j=i+1; j if(arr[j] < arr[minIndex]) {
minIndex = j;
}
}
if(minIndex != i) { //如果minIndex不为i，说明找到了更小的值，交换之。
swap(arr, i, minIndex);
}
}
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
二、选择排序
选择排序的思想其实和冒泡排序有点类似，都是在一次排序后把小的元素放到前面，但是过程不同，冒泡排序是通过相邻的比较和交换，而选择排序是通过对整体的选择。
举个例子，对5,3,8,6,4这个无序序列进行简单选择排序，首先要选择5以外的小数来和5交换，也就是选择3和5交换，一次排序后就变成了3,5,8,6,4.对剩下的序列一次进行选择和交换，终就会得到一个有序序列。
其实选择排序可以看成冒泡排序的优化，因为其目的相同，只是选择排序只有在确定了小数的前提下才进行交换，大大减少了交换的次数。选择排序的时间复杂度为O(n^2)
public class SelectSort {
public static void selectSort(int[] arr) {
if(arr == null || arr.length == 0)
return ;
int minIndex = 0;
for(int i=0; i minIndex = i;
for(int j=i+1; j if(arr[j] < arr[minIndex]) {
minIndex = j;
}
}
if(minIndex != i) { //如果minIndex不为i，说明找到了更小的值，交换之。
swap(arr, i, minIndex);
}
}
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
三、快速排序
快速排序一听名字就觉得很高端，在实际应用当中快速排序确实也是表现的排序算法。冒泡排序虽然高端，但其实其思想是来自冒泡排序，冒泡排序是通过相邻元素的比较和交换把小的冒泡到顶端，而快速排序是比较和交换小数和大数，这样一来不仅把小数冒泡到上面同时也把大数沉到下面。
举个例子：对5,3,8,6,4这个无序序列进行快速排序，思路是右指针找比基准数小的，左指针找比基准数大的，交换之。
5,3,8,6,4 用5作为比较的基准，终会把5小的移动到5的左边，比5大的移动到5的右边。
5,3,8,6,4 首先设置i,j两个指针分别指向两端，j指针先扫描(思考一下为什么?)4比5小停止。然后i扫描，8比5大停止。交换i,j位置。
5,3,4,6,8 然后j指针再扫描，这时j扫描4时两指针相遇。停止。然后交换4和基准数。
4,3,5,6,8 一次划分后达到了左边比5小，右边比5大的目的。之后对左右子序列递归排序，终得到有序序列。
上面留下来了一个问题为什么一定要j指针先动呢?首先这也不是的，这取决于基准数的位置，因为在两个指针相遇的时候，要交换基准数到相遇的位置。一般选取个数作为基准数，那么就是在左边，所以相遇的数要和基准数交换，那么相遇的数一定要比基准数小。所以j指针先移动才能先找到比基准数小的数。
快速排序是不稳定的，其时间平均时间复杂度是O(nlgn)。
public class QuickSort {
//一次划分
public static int partition(int[] arr, int left, int right) {
int pivotKey = arr[left];
int pivotPointer = left;
while(left < right) {
while(left < right && arr[right] >= pivotKey)
right --;
while(left < right && arr[left] <= pivotKey)
left ++;
swap(arr, left, right); //把大的交换到右边，把小的交换到左边。
}
swap(arr, pivotPointer, left); //把pivot交换到中间
return left;
}
public static void quickSort(int[] arr, int left, int right) {
if(left >= right)
return ;
int pivotPos = partition(arr, left, right);
quickSort(arr, left, pivotPos-1);
quickSort(arr, pivotPos+1, right);
}
public static void sort(int[] arr) {
if(arr == null || arr.length == 0)
return ;
quickSort(arr, 0, arr.length-1);
}
public static void swap(int[] arr, int left, int right) {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
}
其实上面的代码还可以再优化，上面代码中基准数已经在pivotKey中保存了，所以不需要每次交换都设置一个temp变量，在交换左右指针的时候只需要先后覆盖就可以了。
这样既能减少空间的使用还能降低赋值运算的次数。优化代码如下：
public class QuickSort {
public static int partition(int[] arr, int left, int right) {
int pivotKey = arr[left];
while(left < right) {
while(left < right && arr[right] >= pivotKey)
right --;
arr[left] = arr[right]; //把小的移动到左边
while(left < right && arr[left] <= pivotKey)
left ++;
arr[right] = arr[left]; //把大的移动到右边
}
arr[left] = pivotKey; //把pivot赋值到中间
return left;
}
public static void quickSort(int[] arr, int left, int right) {
if(left >= right)
return ;
int pivotPos = partition(arr, left, right);
quickSort(arr, left, pivotPos-1);
quickSort(arr, pivotPos+1, right);
}
public static void sort(int[] arr) {
if(arr == null || arr.length == 0)
return ;
quickSort(arr, 0, arr.length-1);
}
}
四、插入排序
插入排序不是通过交换位置而是通过比较找到合适的位置插入元素来达到排序的目的的。相信大家都有过打扑克牌的经历，特别是牌数较大的。
在分牌时可能要整理自己的牌，牌多的时候怎么整理呢?就是拿到一张牌，找到一个合适的位置插入。这个原理其实和插入排序是一样的。
举个例子，对5,3,8,6,4这个无序序列进行简单插入排序，首先假设个数的位置时正确的，想一下在拿到张牌的时候，没必要整理。
然后3要插到5前面，把5后移一位，变成3,5,8,6,4.想一下整理牌的时候应该也是这样吧。然后8不用动，6插在8前面，8后移一位，4插在5前面，从5开始都向后移一位。
注意在插入一个数的时候要保证这个数前面的数已经有序。简单插入排序的时间复杂度也是O(n^2)。
public class InsertSort {
public static void insertSort(int[] arr) {
if(arr == null || arr.length == 0)
return ;
for(int i=1; i
int j = i;
int target = arr[i]; //待插入的
//后移
while(j > 0 && target < arr[j-1]) {
arr[j] = arr[j-1];
j --;
}
//插入
arr[j] = target;
}
}
}
以上就是达内科技java培训班的讲师给大家介绍的关于java常见的排序法，大家可以在看这篇文章的同时也可以点击我们文章下面的获取试听资格按钮来获取我们java培训班的免费试听资格，来免费试听我们的java课程，和我们的讲师进行面对面的交流和互动。也可以来我们的公司进行实地考察深入的了解我们达内科技。
