四个基本的排序算法
/**
* 排序的基本实现方法:插入、选择、冒泡、快速
*/
public class SortImpl {
/**目标待排序数组*/
private static int[] arr = {1,3,4,44,2,33,4,35};
public static void show(int [] arr){
for (int i = 0; i < arr.length; i++){
System.out.print(arr[i] + " ");
}
System.out.println();
}
//一、插入排序 【先确定前面】
//思路: 在要排序的一组数中，假设前面(n-1)[n从2计算] 个数已经是排序的，要把第n个数插到前面的有序数中，使得这 n个数
//也是排好序的。！优势在于碰到它大于前面的数，就直接添加到此数的前面即可。否则一路进行交换处理,直至换到第一位
@Test
public void test1(){
for (int i = 1; i < arr.length; i++) { //插入的值，从i -> lenth -1
for (int j = i; j > 0 && arr[j]<arr[j-1]; j--){
int temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
}
}
show(arr);
}
//二、选择排序 【先确定前面】
//思路:外层遍历所有的元素，然后取出的元素和它后面的元素进行比较，找到最小值。最后放入第一位...N位
@Test
public void test2(){
for (int i = 0; i < arr.length; i++) {
int min = i;
for (int j = i+1 ; j < arr.length; j++) {
if(arr[j]<arr[min]){
min = j;
}
}
if(i!=min){
int temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
}
show(arr);
}
//三、冒泡排序 【先确定后面】
//思路:每次从第一个，持续和它的下一个比较，如果它比下一个大就交换，一次循环算出它尾部最大值。一共n-1次
//外层只控制遍历次数，内层用相邻2个数比较。
@Test
public void test3(){
for (int i = 0; i < arr.length-1; i++) { //1个数时不需要操作。
for (int j = 0; j < arr.length-1-i; j++) { //-i是因为每次可以算一个最大的值，-1是防止越界
if(arr[j+1]<arr[j]){
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
show(arr);
}
//四、快速排序:
@Test
public void test4(){
sortQuick(arr,0,arr.length-1);
show(arr);
}
/**
* 快速排序；分割数组 ----------详细看下面补充的示意图
* @param datas
*/
public static int QuickPartition(int[] datas, int left, int right) {
int key = datas[left]; //基准位
while (left < right) {
while (left < right && datas[right] >= key){
--right;
}
datas[left] = datas[right]; // 将比基准小的元素移到低位，此时right位应=key,会被下面赋值替换，所以不用进行一个完整的换位置。
while (left < right && datas[left] <= key){
++left;
}
datas[right] = datas[left]; // 将比基准大的元素移到高位，此时left应=key，同上理,会被后续赋值替换，只进行一般的换位置。
}
datas[left] = key; // 当left == right，完成一趟快速排序，此时需要补上基准值。
return left;
}
/**
* 快速排序；递归返回数组
* @param datas
*/
public static int[] sortQuick(int[] datas, int left, int right) {
if (left < right) {
int data = QuickPartition(datas, left, right);
sortQuick(datas, left, data - 1);
sortQuick(datas, data + 1, right);
}
return datas;
}
}
补充示意图：快速排序
