java常见的排序算法（一）选择排序，冒泡排序，插入排序，希尔排序

1.选择排序
所有排序中最简单也是最没有用的一种排序算法，主要的思想就是，多次循环，依次找出最大致最小的值。时间复杂度为n的平方

private static int[] sortArray(int[] arr){    for (int i = 0; i < arr.length; i++) { int min=arr[i]; for (int j = i+1; j < arr.length; j++) {     if (min>=arr[j]){  min = arr[j];  arr[j] = arr[i];  arr[i] = min;     } }    }    return arr;}

2.冒泡排序
主要思想就是依次比较相邻两位，满足条件就交换。这种方式由于需要两两比较两两交换，效率比较慢。

private static int[] bullingSortArray(int[] needSort){    for (int i = needSort.length-1; i >0 ; i--) { boolean isAlreadyDown = true; for (int j = 0; j < i; j++) {     if (needSort[j]>needSort[j+1]){  needSort[j]= needSort[j]^needSort[j+1];  needSort[j+1]= needSort[j]^needSort[j+1];  needSort[j]= needSort[j]^needSort[j+1];  isAlreadyDown = false;     } } if (isAlreadyDown) break;    }    return needSort;}

3.插入排序
这种排序的实现有点类似于冒泡排序，循环将后面的值往前排到值该有的地方
对于基本有序的数组且样本小的时候效率比较高，此排序稳定
如下数组[1,3,9,4,6,5]

找到数字4，插入到前面已有序的数列3和9之间，以此类推，将6与5分别插入到相应的位置。
当然在程序的实现上有点类似于冒泡排序，在空间和时间复杂度上其实与冒泡排序也是一致的。

private static int[] insertSort(int[] needSortArray){    for (int i = 1; i < needSortArray.length; i++) { for (int j = i - 1; j >= 0; j--) {     if (needSortArray[j] <= needSortArray[j + 1]) break;     needSortArray[j] = needSortArray[j] ^ needSortArray[j + 1];     needSortArray[j + 1] = needSortArray[j] ^ needSortArray[j + 1];     needSortArray[j] = needSortArray[j] ^ needSortArray[j + 1]; }    }    return needSortArray;}

4.希尔排序
其实就是特殊的一种插入排序的一种，不稳定。只是采用间隔的形式减少交换次数，最大间隔位while(gap<length/3){gap=gap*3+1}

如图，从第一个开始采用间隔为4选取数，形成一组，采用插入排序排好顺序，然后从第二个开始采用间隔为4选取数，形成一组排好顺序，依次类推。
然后将间隔缩小，如缩小到2，再次排序，最终间隔为1最后排一次
如何定义这个间隔序列：Knuth序列
h = 3*h+1;

private static int[] shellSort(int[] needSort) {    int gapNum = 1;    while (gapNum<needSort.length/3){ gapNum = gapNum *3 +1;    }    for (int gap = gapNum; gap >0 ; gap=(gap-1)/3) { for (int i = gap; i < needSort.length; i++) {     for (int j = i; j > gap-1; j-=gap) {  if (needSort[j]>=needSort[j-gap])break;  needSort[j] = needSort[j] ^ needSort[j-gap];  needSort[j-gap] = needSort[j] ^ needSort[j-gap];  needSort[j] = needSort[j] ^ needSort[j-gap];     } }    }    return needSort;}

创作挑战赛 新人创作奖励来咯，坚持创作打卡瓜分现金大奖艺术字体转换器