快排、冒泡、选择、插入、归并、堆
https://leetcode.cn/problems/sort-an-array/
快排
int partition(int arr[], int left, int right) {? ?//找基准数 划分?
????int i = left + 1 ;? ?
????int j = right;? ?
????int temp = arr[left];? ?
????while(i <= j)? ? {? ? ? ?
????????while (arr[i] < temp)? ? ? ? {? ? ? ? ?
? ????????????i++;? ? ? ??
? ? ? ? }? ? ? ?
????????while (arr[j] > temp )? ? ? ? {? ? ? ? ?
????????????? j--;
? ? ? ? }? ? ?
? ? ? ? if (i < j)? ? ? ? ? ?
????????????swap(arr[i++], arr[j--]);? ? ?
? ? ? ? else
?????????????i++;?
? ? ? }? ?
? ? ?swap(arr[j], arr[left]);?
? ? ?return j;??
}
void quick_sort(int arr[], int left, int right)? {? ?
????if (left > right)? ? ? ?
????????return;? ?
????int j = partition(arr, left, right);? ?
????quick_sort(arr, left, j - 1);? ?
????quick_sort(arr, j + 1, right);
?}
冒泡
????public?static?void?bubbleSort(int?arr[])?{
????????for(int?i?=0?;?i<arr.length-1;?i++)?{?
????????????for(int?j=0;?j<arr.length-1-i?;?j++)?{??
????????????????if(arr[j]>arr[j+1])?{
????????????????????int?temp?=?arr[j];
????????????????????arr[j]=arr[j+1];
????????????????????arr[j+1]=temp;
????????????}
????????????}????
????????}
????}
插入排序：每遍历一个元素，就把它插入前面的已排好队列中
publicstaticvoidsort(int[]?arr){
????????if?(arr?==?null?||?arr.length?<?2)
????????????return;
????????for?(int?i?=?1;?i?<?arr.length;?i++)
????????????for?(int?j?=?i;?j?>?0?&&?arr[j]?<?arr[j?-?1];?j--)
????????????????SwapUtils.swap(arr,?j,?j?-?1);
????}
选择排序：每次标记最小元素小标，和首元素交换
publicstaticvoidsort(int[]?arr){
????????if?(arr?==?null?||?arr.length?<?2)
????????????return;
????????int?minIndex;
????????for?(int?i?=?0;?i?<?arr.length;?i++)?{
????????????minIndex?=?i;
????????????for?(int?j?=?i?+?1;?j?<?arr.length;?j++)
????????????????minIndex?=?arr[minIndex]?>?arr[j]???j?:?minIndex;
????????????SwapUtils.swap(arr,?minIndex,?i);
????????}
????}
归并排序：先分再合并
public?classMergeSort{
????publicstaticvoidmergeSort(int[]?arr){
????????if?(arr?==?null?||?arr.length?<?2)?{
????????????return;
????????}
????????mergeSort(arr,?0,?arr.length?-?1);
????}
????private static void mergeSort(int[]?arr,intl,intr){
????????if?(l?==?r)?{
????????????return;
????????}
????????int?mid?=?l?+?((r?-?l)?>>?1);
????????mergeSort(arr,?l,?mid);
????????mergeSort(arr,?mid?+?1,?r);
????????merge(arr,?l,?mid,?r);
????}
????private static void merge(int[]?arr,intl,intmid,intr){
????????int[]?help?=?new?int[r?-?l?+?1];
????????int?i?=?0;
????????int?p1?=?l;
????????int?p2?=?mid?+?1;
????????while?(p1?<=?mid?&&?p2?<=?r)?{
????????????help[i++]?=?arr[p1]?<=?arr[p2]???arr[p1++]?:?arr[p2++];
????????}
????????while?(p1?<=?mid)?{
????????????help[i++]?=?arr[p1++];
????????}
????????while?(p2?<=?r)?{
????????????help[i++]?=?arr[p2++];
????????}
????????for?(i?=?0;?i?<?help.length;?i++)?{
????????????arr[l?+?i]?=?help[i];
????????}
????}
}
堆排序
堆排序的过程分为两步：
第一步是建堆，将一个无序的数组建立为一个堆
第二步是排序，将堆顶元素取出，然后对剩下的元素进行堆化，反复迭代，直到所有元素被取出为止。