排序算法之希尔排序，快速排序
前言：最近将排序算法复习了一遍，写的可能不好，但为了加深印象下，便写下了这篇文章
希尔排序
int shell_sort(int *data, int length) {
int gap = 0;//分组的跨度
int i = 0, j = 0;
for (gap = length / 2; gap >= 1; gap /= 2) { //分组的次数
for (i = gap; i <= length; i++) { //对每组遍历
for (j = i ; j >= gap ; j -= gap) { //组内排序
if (data[j] < data[j - gap]) {
swap(data[j], data[j - gap]);
}
}
}
}
}复制代码第一步：确定分组的次数，上述图中一共12个元素，共分了3次组
下面这个for循环进行了3次
for (gap = length / 2; gap >= 1; gap /= 2)复制代码
第二步：对每个分组进行遍历
截取了gap=3的时候的此次遍历的情况，循环了9次
for (i = gap; i <= length; i++) { //对每组遍历复制代码第三步：组内排序
for (j = i ; j >= gap && data[j - gap] > data[j]; j -= gap) { //组内排序
swap(data[j], data[j - gap]);
}复制代码这个组内排序是最为关键的地方，类似于插入排序，
取出相同颜色的元素，（设相同元素为a,b,c,d,）
将当前位置的元素(假设为c）一直和前一位元素（b）比较，
如果需要交换则交换前后两个元素的位置，（变为了a,c,b,d）
接着继续比较(a和c的比较)一直交换直到不需要交换为止
这次截取gap=3的时候且i=5的时候来进行分析
这次我们只要分析颜色为深紫的几个元素分析就可以了
快速排序
int quick_sort(int *data, int left, int right) {
//每一次递归， 每调用一次， 确定一个值得正确位置
if (left >= right)
return -1;
int key = data[left];
int lo = left, hi = right;
while (lo < hi) {
while (lo < hi && key < data[hi]) {
hi--;
}
while (lo < hi && key > data[lo]) {
lo++;
}
swap(data[lo], data[hi]);
}
//lo == hi
data[lo] = key;
quick_sort(data, left, lo - 1);
quick_sort(data, lo + 1, right);
}复制代码总代码
#include
#define DATA_ARRAY_LENGTH 12
void swap(int &a, int &b) {
int tmp = a;
a = b;
b = tmp;
return ;
}
void print(int *data) {
for (int i = 0; i < DATA_ARRAY_LENGTH; i ++) {
printf("%4d", data[i]);
}
printf("\n");
}
int shell_sort(int *data, int length) {
int gap = 0;//分组的跨度
int i = 0, j = 0;
for (gap = length / 2; gap >= 1; gap /= 2) { //分组的次数
for (i = gap; i <= length; i++) { //对每组遍历
for (j = i ; j >= gap && data[j - gap] > data[j]; j -= gap) { //组内排序
swap(data[j], data[j - gap]);
}
}
}
}
int quick_sort(int *data, int left, int right) {
//每一次递归， 每调用一次， 确定一个值得正确位置
if (left >= right)
return -1;
int key = data[left];
int lo = left, hi = right;
while (lo < hi) {
while (lo < hi && key < data[hi]) {
hi--;
}
while (lo < hi && key > data[lo]) {
lo++;
}
swap(data[lo], data[hi]);
}
//lo == hi
data[lo] = key;
quick_sort(data, left, lo - 1);
quick_sort(data, lo + 1, right);
}
int quick_sort(int *data, int length) {
quick_sort(data, 0, length - 1);
}
int main() {
int i = 0;
int data[DATA_ARRAY_LENGTH] = {23, 64, 24, 12, 9, 16, 53, 57, 71, 79, 87, 97};
#if 0
shell_sort(data, DATA_ARRAY_LENGTH);
#else
quick_sort(data, DATA_ARRAY_LENGTH);
#endif
for (i = 0; i < DATA_ARRAY_LENGTH; i ++) {
printf("%4d", data[i]);
}
printf("\n");
}
作者：长烟
链接：https://juejin.cn/post/7037473904159359006
伪原创工具 SEO网站优化 https://www.237it.com/