• 微信公众号：美女很有趣。 工作之余，放松一下，关注即送10G+美女照片！

# 排序C++实现

2个月前 (02-26) 18次浏览
``````//插入排序
void insertsort(vector<int>& arr)
{
for (int i = 1; i < arr.size(); i++)
{
int key = arr[i];
int end = i - 1;
while (key < arr[end])
{
arr[end + 1] = arr[end];
--end;
if (end < 0)
break;
}
arr[end + 1] = key;
}
}

//选择排序
void selectSort(vector<int>& arr)
{
for (int i = 0; i < arr.size(); i++)
{
int min = i;
for (int j = i; j < arr.size(); j++)
{
if (arr[j] < arr[min])
min = j;
}
swap(arr[i], arr[min]);
}
}

//堆排序
void ad_down(size_t pos, vector<int>& arr, size_t size);
void heap_sort(vector<int>& arr)
{
//建堆
int pos_end = (arr.size() - 2) / 2;
for (int pos = pos_end; pos >= 0; pos--)
{
}
//堆排序
size_t pos_end2 = arr.size() - 1;
while (pos_end2 > 0)
{
swap(arr[0], arr[pos_end2]);
pos_end2--;
}
}

//向下调整
{
size_t parent_pos = pos;
size_t child_pos = pos * 2 + 1;
while (child_pos < size)
{
if (child_pos<size-1 && arr[child_pos] < arr[child_pos + 1])
child_pos++;
if (arr[parent_pos] < arr[child_pos])
{
swap(arr[parent_pos], arr[child_pos]);
parent_pos = child_pos;
child_pos = child_pos * 2 + 1;
}
else
{
break;
}
}
}

//冒泡排序
void bubble_sort(vector<int>& arr)
{
int n = arr.size();
while (n--)
{
bool no_swap = 1;
for (int i = 0; i < n; i++)
{
if (arr[i] > arr[i + 1])
{
swap(arr[i], arr[i + 1]);
no_swap = 0;
}
}
if (no_swap)
break;
}
}

//快速排序
//三数取中
size_t quick_mid(vector<int>& arr, size_t left, size_t right)
{
int mid_num = arr[(right - left) / 2];
int a = left, b = right-1, c = (right - left) / 2;
if (arr[a] < arr[b])
{
if (arr[a] < arr[c])
{
if (arr[b] < arr[c])
return b;
else if (arr[b] >= arr[c])
return c;
}
else if (arr[a] >= arr[c])
return a;
}
else if (arr[a] >= arr[b])
{
if (arr[a] < arr[c])
return a;
else if (arr[a] >= arr[c])
{
if (arr[b] < arr[c])
return c;
else if (arr[b] >= arr[c])
return b;
}
}
}

//hore法
size_t divide_hore(vector<int>& arr, size_t left, size_t right)
{
int pos = quick_mid(arr,left,right);
swap(arr[pos], arr[right-1]);
int key = arr[right-1];
size_t begin = left, end = right-1;
while (begin < end)
{
while (begin < end && arr[begin] <= key)
begin++;
while (begin < end && arr[end] >= key)
end--;
swap(arr[begin], arr[end]);
}
swap(arr[begin], arr[right-1]);
return begin;
}

//挖坑法
size_t divide_potholing(vector<int>& arr, size_t left, size_t right)
{
int pos = quick_mid(arr, left, right);
swap(arr[pos], arr[right - 1]);
size_t begin = left, end = right - 1;
int key = arr[end];
while (begin < end)
{
while (begin < end && arr[begin] <= key)
begin++;
if (begin < end)
{
arr[end] = arr[begin];
end--;
}
while (begin < end && arr[end] >= key)
end--;
if (begin < end)
{
arr[begin] = arr[end];
begin++;
}
}
arr[begin] = key;
return begin;
}

//前后指针法
size_t divide_pointer(vector<int>& arr, size_t left, size_t right)
{
int pos = quick_mid(arr, left, right);
swap(arr[pos], arr[right - 1]);
int key = arr[right - 1];
size_t cur = left;
size_t prev = left - 1;
while (cur < right)
{
if (arr[cur] < key && ++prev != cur)
swap(arr[cur], arr[prev]);
cur++;
}
swap(arr[++prev], arr[right - 1]);
return prev;
}

//快速排序递归调用
void quick_sort_recursion(vector<int>& arr,size_t begin,size_t end)
{
if (end-begin > 1)
{
size_t div = divide_pointer(arr, begin, end);
quick_sort_recursion(arr,begin, div);
quick_sort_recursion(arr, div + 1, end);
}
}

//快速排序循环调用
void quick_sort_loop(vector<int>& arr, size_t begin, size_t end)
{
stack<size_t> s;
s.push(begin);
s.push(end);
while (!s.empty())
{
size_t right = s.top();
s.pop();
size_t left = s.top();
s.pop();
if (right - left > 1)
{
int div = divide_pointer(arr, left, right);
s.push(left);
s.push(div);
s.push(div + 1);
s.push(right);
}
}
}

//归并
void merge_data(vector<int>& arr, size_t left, size_t mid, size_t right, int* tmp)
{
size_t begin1 = left, end1 = mid;
size_t begin2 = mid, end2 = right;
size_t index = left;
while (begin1 < end1 && begin2 < end2)
{
if (arr[begin1] <= arr[begin2])
tmp[index++] = arr[begin1++];
else
tmp[index++] = arr[begin2++];
}
while (begin1 < end1)
tmp[index++] = arr[begin1++];
while (begin2 < end2)
tmp[index++] = arr[begin2++];
}

void _merge_sort(vector<int>& arr, size_t begin, size_t end, int* tmp)
{
if (end - begin > 1)
{
size_t mid = begin+((end - begin) >> 1);
_merge_sort(arr, begin, mid, tmp);
_merge_sort(arr, mid, end, tmp);
merge_data(arr, begin, mid, end, tmp);

memcpy(&arr[0]+begin, tmp+begin, sizeof(arr[0])*(end-begin));
}
}

void merge_sort(vector<int>& arr)
{
int* p = new int[sizeof(arr)];
_merge_sort(arr, 0, arr.size(), p);
delete[] p;
}``````

0

0 收藏

QQ

### 作者的其它热门文章

C++auto，for范围循环，指针空值
【项目】——智能AI语音管家tamako
C语言在函数形参列表用结构体类型定义变量报错的问题
c语言循环判断语句常见习题