不知不觉都过了一年了，只能感叹时光易逝啊。
10号要去软件园那边应聘实习生，所以今天晚上抽点时间复习了一遍常用的排序。
一. 冒泡
void MaoPao(int *nums, int length)
{
for (int i = length-2; i > 0; i--)
{
for (int j = 0; j <= i; j++)
{
if (nums[j + 1] < nums[j])
{
swap(&nums[j], &nums[j+1]);
}
}
}
}
这是最基础也是最容易想到的排序之一。时间(n²)，没啥好说的。
二. 选择
void XuanZhe(int *nums, int length)
{
int minIndex = 0;
bool changed = false;
for (int i = 0; i < length-1; i++)
{
changed = false;
minIndex = i;
for (int j = i; j < length; j++)
{
if (nums[j] < nums[minIndex])
{
minIndex = j;
changed = true;
}
}
if (changed)
{
swap(&nums[i], &nums[minIndex]);
}
}
}
在冒泡、选择、插入里，选择排序算不错的了，起码对内存的操作没有其他两个那么频繁。
三. 插入
void ChaRu(int *nums, int length)
{
for (int i = 1; i < length; i++)
{
for (int j = 0; j < i; j++)
{
if (nums[i] < nums[j])
{
int temp = nums[i];
for (int k = i; k > j; k--)
nums[k] = nums[k - 1];
nums[j] = temp;
}
}
}
}
插入排序的代码让我想起了大一学C语言的灰暗时光。。。
四. 快排
void KuaiPai_DieDai(int *nums, int start, int end)
{
if (start >= end)
return;
int high = end;
int low = start;
while (low < high)
{
while(nums[high] >= nums[low]&& low < high)
high--;
if(low < high)
swap(&nums[low], &nums[high]);
while (nums[low] <= nums[high] && low < high)
low++;
if (low < high)
swap(&nums[low], &nums[high]);
}
KuaiPai_DieDai(nums, start, low-1);
KuaiPai_DieDai(nums, high+1, end);
}
快排就舒服多了。除了不少的low<high有碍观瞻，不管是复杂度还是代码都算很不错的。
五.归并
void GuiBing_DieDai(int *nums, int start, int end, int* temp)
{
if (start >= end)
return;
int mid = (start + end) / 2;
GuiBing_DieDai(nums, start, mid, temp);
GuiBing_DieDai(nums, mid + 1, end, temp);
int first_low = start;
int first_high = mid;
int second_low = mid+1;
int second_high = end;
int tempIndex = 0;
while (first_low <= first_high && second_low <= second_high)
{
if (nums[first_low] < nums[second_low] )
{
temp[tempIndex++] = nums[first_low];
first_low++;
}
else
{
temp[tempIndex++] = nums[second_low];
second_low++;
}
}
while (first_low <= first_high)
{
temp[tempIndex++] = nums[first_low];
first_low++;
}
while (second_low <= second_high)
{
temp[tempIndex++] = nums[second_low];
second_low++;
}
for (int i = 0; i < tempIndex; i++)
{
nums[start + i] = temp[i];
}
}
归并看起来就不那么舒服了，特别是空间上，除了递归的开销还要加个n。不过好在它是稳定的。
六.堆排序
void HeapAdjust(int *nums, int i, int length)
{
int max = i;
int lchild = i * 2 + 1;
int rchild = i * 2 + 2;
if (lchild < length && nums[lchild] > nums[max])
{
max = lchild;
}
if (rchild < length && nums[rchild] > nums[max])
{
max = rchild;
}
if (max != i)
{
int temp;
temp = nums[i];
nums[i] = nums[max];
nums[max] = temp;
HeapAdjust(nums, max, length);
}
}
void Dui(int *nums, int length)
{
for (int i = length / 2 - 1; i >= 0; i--)
{
HeapAdjust(nums, i, length);
}
for (int i = length - 1; i >= 0; i--)
{
swap(&nums[i], &nums[0]);
HeapAdjust(nums, 0, i);
}
}
第一个for循环构建大顶堆，第二个for循环开始排序。
找实习好难啊。。。
原文：https://www.cnblogs.com/charsoul/p/10828949.html