插入排序
void InsertSort(vector<int>& arr)
{
int N = arr.size();
for (int i = 1; i < N; i++)
{
for (int j = i; j > 0; j--)
{
if (arr[j] < arr[j-1])
{
swap(arr[j], arr[j-1]);
}
else
{
break;
}
}
}
}
希尔排序
void ShellSort(vector<int>& arr)
{
int N = arr.size();
int h = 1;
while (h < N/3)
{
h = h * 3 + 1;
}
while (h >= 1)
{
for (int i = 0; i < N; i++)
{
//插入排序
for (int j = i + h; j < N; j = j + h)
{
for (int k = j; k > i; k = k - h)
{
if (arr[k] < arr[k-h])
{
swap(arr[k], arr[k-h]);
}
else
{
break;
}
}
}
}
h /= 3;
}
}
冒泡排序
void BubbleSort(vector<int> &arr)
{
int N = arr.size();
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N - i - 1; j++)
{
if (arr[j] > arr[j+1])
{
swap(arr[j], arr[j+1]);
}
}
}
}
选择排序
void SelectSort(vector<int> &arr)
{
int N = arr.size();
for (int i = 0; i < N - 1; i++)
{
int temp = i;
for (int j = i + 1; j < N; j++)
{
if (arr[temp] > arr[j])
{
temp = j;
}
}
if (i != temp)
{
swap(arr[temp], arr[i]);
}
}
}
快速排序
//快速排序的递归实现和非递归实现
void QuickSortNormal(vector<int>& arr, const int left, const int right)
{
if (left >= right)
{
return;
}
int i = left;
int j = right;
int povit = arr[left];
while(i < j)
{
while (arr[j] >= povit && i < j)
{
j--;
}
while(arr[i] <= povit && i < j)
{
i++;
}
if (i < j)
{
swap(arr[i], arr[j]);
}
}
swap(arr[left], arr[j]);
QuickSortNormal(arr, left, j-1);
QuickSortNormal(arr, j+1, right);
}
//快排的非递归版本实现
void QuickSortNonRes(vector<int> &arr)
{
stack<pair<int, int>> s;
int left = 0;
int right = arr.size()-1;
s.push(make_pair(left, right));
while (!s.empty())
{
pair<int, int> p = s.top();
s.pop();
left = p.first;
right = p.second;
int i = p.first;
int j = p.second;
int povit = arr[left];
while (i < j)
{
while (povit <= arr[j] && i < j)
{
j--;
}
while (povit >= arr[i] && i < j)
{
i++;
}
if (i < j)
{
swap(arr[i], arr[j]);
}
}
swap(arr[left], arr[j]);
if (left < j-1)
{
s.push(make_pair(left, j-1));
}
if (j+1 < right)
{
s.push(make_pair(j+1, right));
}
}
}
归并排序
void MergeTwo(vector<int> arr1, vector<int> arr2, vector<int> &arr)
{
int i = 0;
int j = 0;
while (i < arr1.size() && j < arr2.size())
{
if (arr1[i] < arr2[j])
{
arr.push_back(arr1[i]);
i++;
}
else
{
arr.push_back(arr2[j]);
j++;
}
}
while (i < arr1.size())
{
arr.push_back(arr1[i]);
i++;
}
while (j < arr2.size())
{
arr.push_back(arr2[j]);
j++;
}
}
void MergeSort(vector<int> &arr)
{
int n = arr.size();
if (n < 2)
{
return;
}
vector<int> arr1;
vector<int> arr2;
for (int i = 0; i < n/2; i++)
{
arr1.push_back(arr[i]);
}
for (int i = n/2; i < n; i++)
{
arr2.push_back(arr[i]);
}
MergeSort(arr1);
MergeSort(arr2);
arr.clear();
MergeTwo(arr1, arr2, arr);
}
堆排序
//递归调整成大顶堆
void adjust(vector<int> &arr, int len, int index)
{
int left = index * 2 + 1;
int right = index * 2 + 2;
if (left >= len)
{
return;
}
int maxIndex = index;
if (left < len && arr[left] > arr[maxIndex])
{
maxIndex = left;
}
if (right < len && arr[right] > arr[maxIndex])
{
maxIndex = right;
}
if (maxIndex != index)
{
swap(arr[index], arr[maxIndex]);
adjust(arr, len, maxIndex);
}
}
void heapSort(vector<int> &arr, int len)
{
if (len < 2)
{
return;
}
//把数组调整成大顶堆
for (int i = len/2 - 1; i >= 0; i = i--)
{
adjust(arr, len, i);
}
//交换最大数到最后
swap(arr[len-1], arr[0]);
heapSort(arr, len-1);
}