1.直接插入排序
1.原理：和玩扑克牌一样，从左边第二个牌开始，选中这个，和前面的所有牌比较，插在合适的位置
public static void insertsort(int[] arr){//直接插入排序
for (int i = 1; i < arr.length; i++) {//此循环用来从1开始确定牌的位置
int j = i-1;//得到j前面一个元素
int tmp = arr[i];//将i处元素取出来，用来作比较
for (; j >=0 ; j--) {//此循环用来和i前面的比较，将i放在正确的位置
if(arr[j] > tmp){
arr[j+1] = arr[j];//若i前面的比i大则将前面的值赋值给后面
}else{
// arr[j+1] = tmp;
break;//比前面都要大，没有比较的必要
}
}
arr[j+1] = tmp;//j走完上面循环为-1，上面走完一次循环j=0时为空，
}
}直接插入排序特点
1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)，它是一种稳定的排序算法
4. 稳定性：稳定
2.希尔排序
希尔排序是直接插入排序的Promax版本，将直接插入排序分为n份，比较完n份，排序即成功
思想：先选定一个整数，把待排序文件中所有记录分成多个组，
所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达
=1时，所有记录在统一组内排好序。
public static void shellSort(int[] array){//希尔排序是直接插入排序的优化
int gap = array.length;
while(gap > 0){//将每组距离最终干为1，即可成功
gap /= 2;//得到每组的距离
shell(array,gap);
}
}
public static void shell(int[] array,int gap){
for (int i = gap; i < array.length; i++) {
int tmp = array[i];
int j = i - gap;
for (; j >= 0; j--) {
if(array[j] > tmp){
array[j+gap] = array[j];
}else{
array[j+gap] = tmp;
break;
}
}
array[j+gap] = tmp;
}
}3.选择排序
基本思想：一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元
素排完 。
public static void selsctSort1(int[] array){//选择排序基础版
for (int i = 0; i < array.length; i++) {
int minIndex = i;//每循环一次确定一个从左往右的最小值
int j = i+1;
for (; j <array.length; j++) {
if(array[minIndex] > array[j]){
minIndex = j;//将minTndex和j的下标先进行交换,找到最小的和其交换
}//从一次次循环中得出在[i,length）的最小值
}
swap(array,minIndex,i);
}
}
public static void selsctSort(int[] array){//选择排序promax版
int left = 0;
int right = array.length-1;
while (left < right){
int minIndex = left;
int maxIndex = left;//统一从没排序的起点开始
for (int i = left+1; i < array.length; i++) {
if(array[maxIndex] < array[i]){
maxIndex = i;
}
if(array[minIndex] > array[i]){
minIndex = i;
}
}
swap(array,left,minIndex);
swap(array,right,maxIndex);
left++;
right--;
}
}
public static void swap(int[]array ,int minIndex,int j){
int tmp = array[j];
array[j] = array[minIndex];
array[minIndex] = tmp;
}
}总结：
1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：不稳定
4. 堆排序
降序建大堆，升序建小堆
详情思路请看之前写的堆部分
https://mp.****.net/mp_blog/creation/editor/139502440
/**
* 堆排序
* 时间复杂度：O(n*logN)
* 空间复杂度：O(1)
* 稳定性：不稳定
* @param array
*/
public static void heapSort(int[] array) {
createHeap(array);
int end = array.length-1;
while (end > 0) {
swap(array,0,end);
siftDown(array,0,end);
end--;
}
}
private static void createHeap(int[] array) {
for (int parent = (array.length-1-1)/2; parent >= 0; parent--) {
siftDown(array,parent,array.length);
}
}
/**
*
* @param array
* @param parent 每棵子树调整的根节点
* @param length 每棵子树调整的结束节点
*/
private static void siftDown(int[] array, int parent, int length) {
int child = 2 * parent + 1;
while (child < length) {
if(child + 1 < length && array[child] < array[child+1]) {
child++;
}
if(array[child] > array[parent]) {
swap(array, parent, child);
parent = child;
child = 2*parent+1;
}else {
break;
}
}
}6.快速排序
思想：任取待排序元素序列中的某元
素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有
元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
翻译过来实现过程就是取第一个数，分别在头和尾定义一个指针 ，头指针找比第一个数大的（需求就是把小的放在左边所以需要找大的和右边大的交换），尾指针找比第一个小的，两个都找到后，进行交换，确保左边的都是小于或等于第一个数的，右边都是大于或等于第一个数的，直到两个指针位置相等，然后再交换第一个与它们的位置，通过递归将它们分为一个个更小的然后即可完成
快速排序Hoare法实现过程
问题：为什么先从后面开始
如果先从前面开始则会造成最后汇合点大于key.
递归法
通过left和right的不断变化，直到left与right相遇为止，当不断分为很多的left和right后，
public class Sort {
public static void swap(int[]array ,int minIndex,int j){
int tmp = array[j];
array[j] = array[minIndex];
array[minIndex] = tmp;
}
public static void qsort(int[] array){
int left = 0,right = array.length-1;
parttrtions(array,left,right);
}
private static void parttrtions(int[]array,int left,int right){
if(left>=right){
return;
}
int start = parttrtion(array,left,right);
parttrtions(array,left,start-1);
parttrtions(array,start+1,right);
}
private static int parttrtion(int[] array,int left,int right){//Hoare版
int privt = array[left];
int end = right,start = left;
while(start<end){
while(start<end&& array[end] >= privt) {//从右往左直到找到比array[start](privt)小的放在
end--;
}
while(start<end&&array[start] <= privt){//跳出小循环说明找到了比privt大的数
start++;
}
swap(array,left,start);
}
return start;
}
private static int parttrtion1(int[] array,int left,int right){//挖坑法
int privt = array[left];
int end = right,start = left;
while(start<end){
while(start<end&& array[end] >= privt) {//从右往左直到找到比array[start](privt)小的放在
end--;
}
array[start] = array[end];//将end下标的值来补充start的空缺
while(start<end&&array[start] <= privt){//跳出小循环说明找到了比privt大的数
start++;
}
array[end] = privt;//将start下标的值来补充end的空缺
}
return start;
}
}
快排的优化：
1.三数取中法：如果是单一的数则可能造成，单支树的产生，最高造成N(O*2),所以可以提前将中间的值给到start,这样能极大减少计算量
private static int getMiddleNum(int[] array,int left,int right) {
int mid = (left+right)/2;
if(array[left] < array[right]) {
if(array[mid] < array[left]) {
return left;
}else if(array[mid] > array[right]) {
return right;
}else {
return mid;
}
}else {
if(array[mid] > array[left]) {
return left;
}else if(array[mid] < array[right]) {
return right;
}else {
return mid;
}
}
}非递归法
利用栈后进先出不断变化left和right的值
public static void qsort1(int[] array){
int left = 0,right = array.length-1;
int par = parttrtion(array,left,right);
Stack<Integer> stack = new Stack<>();
if(par>left+1){
stack.push(left);
stack.push(par-1);
}
if(par < right-1){
stack.push(par+1);
stack.push(right);
}
while(!stack.empty()){
right = stack.pop();
left = stack.pop();
par = parttrtion(array,left,right);
if(par>left+1){
stack.push(left);
stack.push(par-1);
}
if(par < right-1){
stack.push(par+1);
stack.push(right);
}
}
}
总结：
1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(logN)
4. 稳定性：不稳定
7.归并排序
思想：先将数组分成很多小份，然后再进行排序，然后把排序完的数组重新整和，最终得到一个有序数组。
递归法
1.首先将大数组分为小数组，把大问题拆分为小问题，1.找到最底层的两个数组，2.排序
public void mergeSortTmp(int[]a,int left,int right){//将数组先分开再合并
if(left>=right){
return;
}
int mid = (left+right)/2;
mergeSortTmp(a,left,mid);//分成很多份，找到最左边
mergeSortTmp(a,mid+1,right);//上层递归完成，找到对应要排序的另一个数组
merge(a,mid,left,right);//两个都找到后，进行排序操作
}2.然后利用两个数组组合排序的方法，定义两个指针，取到小的添加到新的数组
private void merge(int[]a,int mid,int left,int right){
int [] array = new int[right-left+1];
int set = 0;
int s1 = left;
int e1 = mid;
int s2 = mid+1;
int e2 = right;
while(s1<e1&&s2<e2){
if(a[s1] < a[s2]){
array[set++] = a[s1++];
}
else {
array[set++] = a[s2++];
}
}
while (s1 <= mid) {
array[set++] = array[s1++];
}
while (s2 <= right) {
array[set++] = array[s2++];
}
for (int i = 0; i < array.length; i++) {
a[i+left] = array[i];//分组后每一小组的下标并不是零
}
}非递归法
思路：我们这个排序的核心就是1.一步步得到最小数组 2.一步步将两个小数组合并起来直到得到 大数组
所以可以在循环里嵌套循环，外面决定数组长度，里面循环将小数组排序合并，外循环设置每个小数组的相隔距离
public void mergrSort1(int[] array){
int left = 0,right = array.length-1;
int gap = 1;//gap负责将数组分为array.length/2
while(gap<array.length){
for (int i = 0; i < array.length; i+=2*gap) {//得到小一号的数组并且进行排序合并,里面for循环是为了得到最多组数组
left = i;
int mid = left+gap-1;
right = mid+gap;
if(mid >= array.length) mid=array.length-1;
if(right>=array.length) right = array.length-1;
merge(array,mid,left,right);
}
gap *= 2;//世界线收束，每次小数组排序好后，再将更大数组排序
}
}
}总结：1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(N)
4. 稳定性：稳定
8.计数排序
思路：将原数组遍历一遍，得到原数组的最大值和最小值，将最大值和最小值相减，得到它们的取值范围，创建一个新数组，然后将对应的值给到，和其相对相等的下标，（比如数组的值为1给到开辟数组的1下标，）然后遍历新数组，赋值给原数组
/**
* 计数排序：
* 时间复杂度：O(范围 + n )
* 范围越大 越慢
* 空间复杂度：O(范围)
* 稳定性：
* @param array
*/
public static void countSort(int[] array) {
//1. 找最大值 和 最小值 来确定 计数数组的大小
int maxVal = array[0];
int minVal = array[0];
for (int i = 1; i < array.length; i++) {
if(array[i] < minVal) {
minVal = array[i];
}
if(array[i] > maxVal) {
maxVal = array[i];
}
}
int len = maxVal - minVal + 1;
int[] count = new int[len];
//2. 遍历原来的数组array把 每个元素 放到对应的计数数组当中 进行计数
for (int i = 0; i < array.length; i++) {
int index = array[i];
count[index-minVal]++;
}
//3.依次 遍历计数数组 O(范围)
int index = 0;
for (int i = 0; i < count.length; i++) {
while (count[i] != 0) {
array[index] = i+minVal;
index++;
count[i]--;
}
}
}
总结
1. 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
2. 时间复杂度：O(MAX(N,范围))
3. 空间复杂度：O(范围)
4. 稳定性：稳定