基本思想：每次遍历都与前面的元素进行比较并插入到合适的位置，该位置之后的元素对应进行后移一位。
图示：
代码：
/* * 直接插入排序(基本有序时效率高) */ void insertSort(int* arr, int size){ for (int i = 1; i < size; i++){ int j = i - 1; while(j >= 0 && arr[i] < arr[j]){ j--; } if(j != i - 1){ int temp = arr[i]; for (int k = i; k > j + 1; k--){ arr[k] = arr[k - 1]; } arr[j + 1] = temp; } } }
基本思想：先将整个待排对象序列按照一定间隔分割成为若干子序列，分别进行直接插入排序，然后缩小间隔，对整个对象序列重复以上的划分子序列和分别排序工作，直到最后间隔为1，此时整个对象序列已 “基本有序”，进行最后一次直接插入排序。
图示：
代码：
/* * 希尔排序(前：数量少，速度快；后：基本有序，效率高) */ void shellSort(int *arr, int size, int gap){ for (int g = gap; g > 0; g--){ for (int i = g; i < size; i += g){ int j = i - g; while (j >= 0 && arr[i] < arr[j]){ j -= g; } if (j != i - g){ int temp = arr[i]; for (int k = i; k > j + g; k -= g){ arr[k] = arr[k - g]; } arr[j + g] = temp; } } } }
基本思想：一共需要n-1趟遍历，依次前后两两比较，每趟遍历的元素对的个数会逐渐减一，因为每次遍历都会将当前最值移动到遍历序列的最后面。
图示：
代码：
/* * 冒泡排序(优化：1.有序标记，判断是否可以提前结束；2.最后一次交换的位置，避免在有序区域进行冗余比较) */ void bubbleSort(int *arr, int size){ int lastExchangeIdex = 0; // 最后一次交换的位置 int border = size; for (int i = 0; i < size - 1; i++){ bool isSorted = true; // 有序标记 for (int j = 1; j < border; j++){ if(arr[j] < arr[j - 1]){ int temp = arr[j]; arr[j] = arr[j - 1]; arr[j - 1] = temp; isSorted = false; lastExchangeIdex = j; } } border = lastExchangeIdex; if(isSorted) break; } }
基本思想：先选出一个哨兵（pivot），然后将比它小的元素分别放在它的左边，比它大的元素放在它的右边，以此类推地二分下去。实现的关键在于如何遍历使得元素分居哨兵的两侧，可参考博客面试常考算法题(三)--快速排序
代码：
/* * 快速排序(最坏时间复杂度为O(N^2)；平均时间复杂度为O(NlogN)) */ void quickSort(int *arr, int begin, int end){ if(begin >= end) return; int pivot = arr[begin]; int i = begin + 1; int j = end; while(i != j){ if(arr[j] > pivot){ j--; continue; } else{ if(arr[i] < pivot){ i++; continue; } else{ int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; j--; } } } int mid; if(arr[i] < pivot){ arr[begin] = arr[i]; arr[i] = pivot; mid = i; } else{ arr[begin] = arr[i - 1]; arr[i - 1] = pivot; mid = i - 1; } quickSort(arr, begin, mid - 1); quickSort(arr, mid + 1, end); }按照这种二分的思想我们还可以设计出求无序数组的顺序第k个数（求中位数是一种特殊的情况），时间复杂度为O(NlogN)。
代码：
/* * 获取第k个元素 */ int getKthElement(int *arr, int size, int k){ int begin = 0; int end = size - 1; while(true){ if(begin == end){ return arr[begin]; // 如果范围收缩到单个位置，那么这个元素即为所求 } int pivot = arr[begin]; int i = begin + 1; int j = end; while(i != j){ if(arr[j] > pivot){ j--; continue; } else{ if(arr[i] < pivot){ i++; continue; } else{ int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; j--; } } } int mid; if(arr[i] < pivot){ arr[begin] = arr[i]; arr[i] = pivot; mid = i; } else{ arr[begin] = arr[i - 1]; arr[i - 1] = pivot; mid = i - 1; } if(mid == k){ return pivot; } else if(mid < k){ begin = mid + 1; } else{ end = mid - 1; } } }
