基本思想:通过两辆比较相邻元素的关键字,如果反序则交换,直到没有反序的元素为止。
简单选择排序基本思想:在第i次循环中,选取其中最小的关键字的记录,作为有序序列的第i个元素。相比较冒泡排序,它大的特点是减少了移动交换的次数。
直接插入排序基本思想:将一个元素直接插入到已经排好的有序表中,从而得到一个新的、元素数增1的有序表。
即使这三种排序方法的时间复杂度都是o( n 2 n^2 n2),但在性能上直接插入排序 >简单选择排序 >冒泡排序
代码实现#include#include#define MAXSIZE 10000
#define DATALEN 10
typedef struct SqList
{int data[MAXSIZE + 1]; // 下标0用于存放临时变量或哨兵
int length;
} SqList;
void SwapData(SqList *L, int i, int j)
{int temp = L->data[j];
L->data[j] = L->data[i];
L->data[i] = temp;
}
void BubbleSort(SqList *L)
{int isSwap = 1; //交换标志,若在一次循环中未发生交换,则说明排序已经结束
for (int i = 1; i< L->length && isSwap; i++)
{isSwap = 0;
for (int j = L->length - 1; j >= i; j--)
{if (L->data[j + 1]< L->data[j])
{SwapData(L, j, j + 1);
isSwap = 1;
}
}
}
}
void SelectSort(SqList *L)
{int min = 0;
for (int i = 1; i< L->length; i++)
{min = i;
for (int j = i + 1; j<= L->length; j++)
{if (L->data[j]< L->data[min])
{min = j;
}
}
if (min != i)
{SwapData(L, i, min);
}
}
}
void InsertSort(SqList *L)
{for (int i = 1; i< L->length; i++)
{if (L->data[i + 1]< L->data[i])
{L->data[0] = L->data[i + 1];
int j;
for (j = i; L->data[j] >L->data[0]; j--)
{L->data[j + 1] = L->data[j];
}
L->data[j + 1] = L->data[0];
}
}
}
int main()
{int a[DATALEN] = {1, 5, 8, 4, 2, 0, 3, 7, 6, 9};
SqList *L = (SqList *)malloc(sizeof(SqList));
for (int i = 0; i< DATALEN; i++)
{L->data[i + 1] = a[i];
}
L->length = DATALEN;
// 冒泡排序
// BubbleSort(L);
// 简单选择排序
// SelectSort(L);
// 直接插入排序
// InsertSort(L);
for (int i = 1; i<= L->length; i++)
{printf("%d ", L->data[i]);
}
return 0;
}
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧