. - 力扣（LeetCode）
?
這道題我們可以使用我們學過的那些常見的排序方法來進行解答?
//插入排序
void InsertSort(int* nums, int n)
{for (int i = 0; i < n-1; i++){int end = i;int tmp = nums[end + 1];while (end >= 0){if (tmp < nums[end]){nums[end + 1] = nums[end];}else{break;}}end--;}
}//希爾
void ShellSort(int* nums, int numsSize)
{int gap = numsSize;while(gap > 1){gap = gap/2;for(int i =0; i < numsSize - gap; i++){int end = i;int tmp = nums[end+gap];while(end >= 0){if(tmp < nums[end]){nums[end + gap] = nums[end];end -= gap;}else{break;}}nums[end+gap] = tmp;}}
}void Swap(int* a ,int* b)
{int tmp = *a;*a = *b;*b = tmp;
}//選擇排序
void SelectSort(int* nums, int n)
{int left = 0;int right = n-1;while(left < right){int maxi = left, mini = left;for(int i=left+1; i<=right; i++){if(nums[i] > nums[maxi]){maxi = i;}if(nums[i] < nums[mini]){mini = i;}}Swap(&nums[left], &nums[mini]);if(maxi == left){maxi = mini;}Swap(&nums[right], &nums[maxi]);++left;--right;}
}int GetMidi(int* nums, int left, int right)
{int midi = (left + right) / 2;if(nums[left] < nums[midi]){if(nums[midi] < nums[right]){return midi;}else if(nums[left] < nums[right]){return right;}else{return left;}}else{if(nums[midi] > nums[right]){return midi;}else if(nums[left] < nums[right]){return left; }else{return right;}}
}int PartSort(int* nums, int left, int right)
{int midi = GetMidi(nums, left, right);Swap(&nums[midi], &nums[left]);int keyi = left;while(left < right){while(left < right && nums[right] >= nums[keyi]){right--;}while(left < right && nums[left] <= nums[keyi]){left++;}Swap(&nums[left],&nums[right]);}Swap(&nums[keyi],&nums[left]);return left;// int keyi = left;// int prev = keyi;// int cur = prev+1;// while(cur <= right)// {// if(nums[cur] < nums[keyi] && ++prev != cur)// {// Swap(&nums[prev],&nums[cur]);// }// ++cur;// }// Swap(&nums[prev],&nums[keyi]);// return prev;
}//快速排序
void QuickSort(int* nums, int begin, int end)
{if(begin >= end){return;}// if((end - begin + 1) > 10)// {// int keyi = PartSort(nums, begin, end);// QuickSort(nums, begin, keyi-1);// QuickSort(nums, keyi+1, end);// }// else// {// InsertSort(nums + begin, end - begin + 1);// }int keyi = PartSort(nums, begin, end);QuickSort(nums, begin, keyi-1);QuickSort(nums, keyi+1, end);
}void _MergeSort(int* nums, int* tmp, int begin, int end)
{if(end <= begin){return;}int mid = (begin + end) / 2;_MergeSort(nums, tmp, begin, mid);_MergeSort(nums, tmp, mid+1, end);int begin1 = begin, end1 = mid;int begin2 = mid+1, end2 = end;int index = begin;while(begin1 <= end1 && begin2 <= end2){if(nums[begin1] < nums[begin2]){tmp[index++] = nums[begin1++];}else{tmp[index++] = nums[begin2++];}}while(begin1 <= end1){tmp[index++] = nums[begin1++];}while(begin2 <= end2){tmp[index++] = nums[begin2++];}memcpy(nums+begin, tmp+begin, sizeof(int)*(end-begin+1));
}//歸并排序
void MergeSort(int* nums, int n)
{int* tmp = (int*)malloc(sizeof(int)*n);_MergeSort(nums, tmp, 0, n-1);free(tmp);}計數排序
void CountSort(int* nums, int n)
{int min = nums[0], max = nums[0];for(int i = 0; i<n;i++){if(nums[i] < min){min = nums[i];}if(nums[i] > max){max = nums[i];}}int range = max - min + 1;int* tmp = (int*)malloc(sizeof(int)*range);memset(tmp, 0, sizeof(int)*range);for(int i =0;i<n;i++){tmp[nums[i] - min]++; }int j = 0;for(int i =0;i<range;i++){while(tmp[i]--){nums[j++] = i + min;}}
}?
)
