标签：item gif int ++i const 右值 简单 img inf
数据结构八大排序中的图解
1.排序的基本概念
2.交换类排序法
? 1-冒泡排序
? 2-快速排序
#include
#include
#include
int stack[512];
int top = 0;
void init_stack()
{
top = 0;
}
void push(int item)
{
stack[top++] = item;
}
int pop(void)
{
return stack[--top];
}
int is_empty(void)
{
return top == 0;
}
//交换
void swap(int *a, int *b)
{
int tmp;
tmp = *a;
*a = *b;
*b = tmp;
}
//打印一个数组
void print_array(int *a, int len)
{
int i;
for (i = 0; i v[j + 1])
{
swap(v + j, v + j + 1);
is_change = 1;
}
}
// print_array(v, len);
}
}
//递归实现快速排序
void quick_sort1(int *v, int left, int right)
{
int key;
int i;
int j;
if (left > right)
{
return;
}
key = v[left];
i = left;
j = right;
//由小到大排序
while(i = key))
{
j--;
}
while((i = key) )
{
j--;
}
if (i = key) )
{
j--;
}
while ((i right)
{
return;
}
i = partition_right(v, left, right);
quick_sort2(v, left, i - 1);
quick_sort2(v, i + 1, right);
}
#define push2(A, B) push(B); push(A);
//迭代的方法实现快速排序
void quick_sort3(int *v, int left, int right)
{
int i;
init_stack();
push2(left, right);
while (!is_empty())
{
left = pop();
right = pop();
if (right right - i)
{
push2(left, i - 1);
push2(i + 1, right);
}
else
{
push2(i + 1, right);
push2(left, i - 1);
}
}
}
int main(int argc, char const *argv[])
{
int v[] = {14, 99, 65, 97, 73, 13, 18, 0, 55, 32, -11, 101, 999, -111, 11, -100, 100, 87, 987, 12, 14, -99, 66};
int a[] = {14, 99, 65, 97, 73, 13, 18, 0, 55, 32, -11, 101, 999, -111, 11, -100, 100, 87, 987, 12, 14, -99, 66};
int len = sizeof(v) / sizeof(v[0]);
print_array(a, len);
memcpy(a, v, sizeof(v));
bubble_sort(a, len);
print_array(a, len);
memcpy(a, v, sizeof(v));
quick_sort1(a, 0, len - 1);
print_array(a, len);
memcpy(a, v, sizeof(v));
quick_sort2(a, 0, len - 1);
print_array(a, len);
memcpy(a, v, sizeof(v));
quick_sort3(a, 0, len - 1);
print_array(a, len);
return 0;
}
◇递归排序
◇迭代排序
◇C语音qsort（）函数
3.插入类排序法
?3-直接插入排序 (Straight Insertion Sort)
?4-希尔排序（Shell Sort）
#include
#include
#include
//交换
void swap(int *a, int *b)
{
int tmp;
tmp = *a;
*a = *b;
*b = tmp;
}
//打印一个数组
void print_array(int *a, int len)
{
int i;
for (i = 0; i pos; j--)
{
a[j] = a[j - 1];
}
a[pos] = current_value;
}
//print_array(a, len);
}
}
void insert_sort2(int *v, int len)
{
int i;
int j = 0;
int current_value;
for(i = 1; i = 0) && (v[j] > current_value); j--)
{
v[j + 1] = v[j] ;
}
v[j + 1] = current_value;
}
//print_array(a, len);
}
}
//折半插入排序
void bin_insert_sort(int *a, int len)
{
int i;
int j;
int current_value;
int low;
int high;
int mid;
for (i = 1; i a[mid])
{
mid = mid + 1;
}
//移动数据
for (j = i; j > mid; j--)
{
a[j] = a[j - 1];
}
//插入数据
a[mid] = current_value;
//print_array(a, len);
}
}
//简单希尔排序
void shell_sort1(int *v, int len)
{
int gap;
int i;
int j;
for (gap = len / 2; gap > 0; gap /= 2)
{
for (i = gap; i = 0; j -= gap)
{
if (v[j] = 0) && (v[j] > current_value); j -= gap)
{
v[j + gap] = v[j];
}
v[j + gap] = current_value;
}
}
}while(gap > 1);
}
int main(int argc, char const *argv[])
{
int v[] = {14, 99, 65, 97, 73, 13, 18, 0, 55, 32, -11, 101, 999,-111,11, -90, 87, -60, 81, -10, 12, -119, 911, 375};
int a[] = {14, 99, 65, 97, 73, 13, 18, 0, 55, 32, -11, 101, 999,-111,11, -90, 87, -60, 81, -10, 12, -119, 911, 375};
int len = sizeof(v) / sizeof(v[0]);
print_array(a, len);
memcpy(a, v, sizeof(v));
insert_sort1(a, len);
print_array(a, len);
memcpy(a, v, sizeof(v));
insert_sort2(a, len);
print_array(a, len);
memcpy(a, v, sizeof(v));
bin_insert_sort(a, len);
print_array(a, len);
memcpy(a, v, sizeof(v));
shell_sort1(a, len);
print_array(a, len);
memcpy(a, v, sizeof(v));
shell_sort2(a, len);
print_array(a, len);
return 0;
}
4.选择类排序法
?5-简单选择排序（Simple Selection Sort）
?6-堆排序（Heap Sort）
#include
#include
#include
//交换
void swap(int *a, int *b)
{
int tmp;
tmp = *a;
*a = *b;
*b = tmp;
}
//打印一个数组
void print_array(int *a, int len)
{
int i;
for (i = 0; i v[i])
{
min = v[i];
min_pos = i;
}
}
return min_pos;
}
//简单选择排序
void simple_select_sort(int *v, int n)
{
int i = 0;
int min_pos;
for (i = 0; i = v[i])
{
break;
}
else
{
v[parent] = v[i];
parent = i;
}
}
//put the value in the final position
v[parent] = root_value;
}
//堆排序主要算法
void heap_sort(int v[], int len)
{
int i;
//1.构建大根堆
for (i = len / 2 - 1; i >= 0; i--)
{
//put the value in the final position
adjust_heap(v, i, len);
}
//2.调整堆结构+交换堆顶元素与末尾元素
for (i = len - 1; i > 0; i--)
{
//堆顶元素和末尾元素进行交换
swap(v, v + i);
adjust_heap(v, 0, i);//重新对堆进行调整
}
}
int main(int argc, char const *argv[])
{
int v[] = {14, 99, 65, 97, 73, 13, 18, 0, 55, 32, -11, 101, 999,-111,11, -90, 87, -60, 81, -10, 12, -119, 911, 375};
int a[] = {14, 99, 65, 97, 73, 13, 18, 0, 55, 32, -11, 101, 999,-111,11, -90, 87, -60, 81, -10, 12, -119, 911, 375};
int len = sizeof(v) / sizeof(v[0]);
print_array(a, len);
memcpy(a, v, sizeof(v));
simple_select_sort(a, len);
print_array(a, len);
memcpy(a, v, sizeof(v));
heap_sort(a, len);
print_array(a, len);
return 0;
}
5.归并排序法
?7-迭代法
?8-递归法
#include
#include
#include
//交换
void swap(int *a, int *b)
{
int tmp;
tmp = *a;
*a = *b;
*b = tmp;
}
//打印一个数组
void print_array(int *a, int len)
{
int i;
for (i = 0; i = high， 不是while，且不含等号，否则死循环
if(low
6.基数排序法
#include
#include
#include
#define MAX_D 4 //最大数是多少位
#define NUM_BUCKET 10 //定义桶的数目，这里是10进制
//交换
void swap(int *a, int *b)
{
int tmp;
tmp = *a;
*a = *b;
*b = tmp;
}
//打印一个数组
void print_array(int *a, int len)
{
int i;
for (i = 0; i MAX_D)
{
return -1;
}
for (i = 0; i = right || k > MAX_D)
{
return;
}
for (i = 0; i = right || k > MAX_D)
{
return;
}
for (i = 0; i = right || k > MAX_D)
{
return;
}
for (; k
八大排序
标签：item gif int ++i const 右值 简单 img inf
原文地址：https://www.cnblogs.com/IvanLxy/p/13611334.html