1、冒泡排序
#include <stdio.h>
#define N 1000
int arr[N];
/* 对长度为n的数组arr执行冒泡排序 */
void bubbleSort(int arr[], int n);
/* 打印长度为n的数组arr */
void printArray(int arr[], int n);
void swap(int *xp, int *yp) {
int temp = *xp;
*xp = *yp;
*yp = temp;
}
int main() {
int n, i;
scanf("%d", &n);
for (i = 0; i < n; ++i) {
scanf("%d", &arr[i]);
}
bubbleSort(arr, n);
printArray(arr, n);
return 0;
}
/* 打印长度为n的数组arr */
void printArray(int arr[], int n) {
int i;
for (i = 0; i < n; i++) {
printf("%d", arr[i]);
if (i < n - 1) /* 下标0..n-2每个元素后面有个空格 */
printf(" "); /*下标n-1,也就是最后一个元素后面没有空格*/
}
printf("\n"); /* 一行打印完后换行 */
}
/* 你的代码将嵌在这里 */
/* 对长度为n的数组arr执行冒泡排序 */
void bubbleSort(int arr[], int n){
for(int i=0;i<n-1;i++){
for(int j=0;j<n-i-1;j++){
if(arr[j]>arr[j+1]){
swap(&arr[j],&arr[j+1]);
}
}
}
}2、简单选择排序
#include<stdio.h>
#include<stdlib.h>
typedef int KeyType;
typedef struct {
KeyType *elem; /*elem[0]一般作哨兵或缓冲区*/
int Length;
}SqList;
void CreatSqList(SqList *L);/*待排序列建立，由裁判实现，细节不表*/
void SelectSort(SqList L);
int main()
{
SqList L;
int i;
CreatSqList(&L);
SelectSort(L);
for(i=1;i<=L.Length;i++)
{
printf("%d ",L.elem[i]);
}
return 0;
}
/*你的代码将被嵌在这里 */
/* 对顺序表L作简单选择排序 */
void SelectSort(SqList L) {
int i, j, minh;
KeyType temp;
for (i = 1; i < L.Length; i++) {
// 寻找[i..Length]区间内的最小元素
minh = i;
for (j = i + 1; j <= L.Length; j++) {
if (L.elem[j] < L.elem[minh]) {
minh = j;
}
}
// 如果最小元素不是当前元素，则交换
if (minh != i) {
temp = L.elem[i];
L.elem[i] = L.elem[minh];
L.elem[minh] = temp;
}
}
}3、快速排序
#include<stdio.h>
#include<stdlib.h>
typedef int KeyType;
typedef struct
{
KeyType *elem; /*elem[0]一般作哨兵或缓冲区*/
int Length;
}SqList;
void CreatSqList(SqList *L);/*待排序列建立，由裁判实现，细节不表*/
int Partition ( SqList L,int low, int high );
void Qsort ( SqList L,int low, int high );
int main()
{
SqList L;
int i;
CreatSqList(&L);
Qsort(L,1,L.Length);
for(i=1;i<=L.Length;i++)
printf("%d ",L.elem[i]);
return 0;
}
void Qsort ( SqList L,int low, int high )
{
int pivotloc;
if(low<high)
{
pivotloc = Partition(L, low, high ) ;
Qsort (L, low, pivotloc-1) ;
Qsort (L, pivotloc+1, high );
}
}
/*你的代码将被嵌在这里 */
int Partition ( SqList L, int low, int high ){
KeyType pivotloc;
pivotloc=L.elem[low];
L.elem[0]=pivotloc;
while(low<high){
while(low<high&&L.elem[high]>=pivotloc){
high--;
}
L.elem[low]=L.elem[high];
while(low<high&&L.elem[low]<=pivotloc){
low++;
}
L.elem[high]=L.elem[low];
}
L.elem[low]=L.elem[0];
return low;
}4、希尔排序的实现
#include<stdio.h>
#include<stdlib.h>
typedef int KeyType;
typedef struct {
KeyType *elem; /*elem[0]一般作哨兵或缓冲区*/
int Length;
}SqList;
void CreatSqList(SqList *L);/*待排序列建立，由裁判实现，细节不表*/
void ShellInsert(SqList L,int dk);
void ShellSort(SqList L);
int main()
{
SqList L;
int i;
CreatSqList(&L);
ShellSort(L);
for(i=1;i<=L.Length;i++)
{
printf("%d ",L.elem[i]);
}
return 0;
}
void ShellSort(SqList L)
{
/*按增量序列dlta[0…t-1]对顺序表L作Shell排序,假设规定增量序列为5,3,1*/
int k;
int dlta[3]={5,3,1};
int t=3;
for(k=0;k<t;++k)
ShellInsert(L,dlta[k]);
}
/*你的代码将被嵌在这里 */
void ShellInsert(SqList L,int dk){
int j;
KeyType t;
for(int i=dk+1;i<=L.Length;i++){
if(L.elem[i]<L.elem[i-dk]){
t=L.elem[i];
j=i-dk;
while(j>0&&L.elem[j]>t){
L.elem[j+dk]=L.elem[j];
j-=dk;
}
L.elem[j+dk]=t;
}
}
}5、插入排序可能出现：在最后一趟开始之前，所有的元素都不在其最终的位置上（设待排元素个数N>2）。
6、对初始数据序列{ 8, 3, 9, 11, 2, 1, 4, 7, 5, 10, 6 }进行希尔排序。若第一趟排序结果为（ 1, 3, 7, 5, 2, 6, 4, 9, 11, 10, 8 ），第二趟排序结果为（ 1, 2, 6, 4, 3, 7, 5, 8, 11, 10, 9 ），则两趟排序采用的增量（间隔）依次是：5,3.
7、时间复杂度不受数据初始状态影响，恒为O(NlogN)的是：堆排序。
8、选择一个排序算法时，除算法的时空效率外，下列因素中，还需要考虑的是：
- I、数据的规模
- II、数据的存储方式
- III、算法的稳定性
- IV、数据的初始状态
9、对N个不同的数据采用冒泡算法进行从大到小的排序，从小到大排好的肯定交换元素次数最多 。
10、对于7个数进行冒泡排序，需要进行的比较次数为：21.
11、
对一组数据(2，12，16，88，5，10)进行排序，若前三趟排序结果如下:
第一趟:2，12，16，5，10，88
第二趟:2，12，5，10，16，88
第三趟:2，5，10，12，16，88
则采用的排序方法可能是冒泡排序。
12、对于7个数进行冒泡排序，最坏情况下需要进行的比较次数为21.
13、对N个元素采用简单选择排序，比较次数和移动次数分别为：O(N^2), O(N)。
14、对于10个数的简单选择排序，最坏情况下需要交换元素的次数为：9.
15、
对大部分元素已有序的数组进行排序时，直接插入排序比简单选择排序效率更高，其原因是：
- (I). 直接插入排序过程中元素之间的比较次数更少
16、设有100个元素的有序序列，如果用二分插入排序再插入一个元素，则最大比较次数是：7.
17、对一组包含10个元素的非递减有序序列，采用直接插入排序排成非递增序列，其可能的比较次数和移动次数分别是：45,44.
18、对于序列{ 49，38，65，97，76，13，27，50 }，按由小到大进行排序，49,13,27,50,76,38,65,97是初始步长为4的希尔排序法第一趟的结果 。
19、对N个记录进行快速排序，在最坏的情况下，其时间复杂度是：O(N^2)。
20、有组记录的排序码为{46，79，56，38，40，84 }，采用快速排序（以位于最左位置的对象为基准而）得到的第一次划分结果为：{40,38,46,56,79,84}。
21、在快速排序的一趟划分过程中，当遇到与基准数相等的元素时，如果左右指针都会停止移动，那么当所有元素都相等时，算法的时间复杂度是O(NlogN)。
22、快速排序方法在要排序的数据已基本有序情况下最不利于发挥其长处。
23、给定初始待排序列{ 15，9，7，8，20，-1，4 }。如果希尔排序第一趟结束后得到序列为{ 15，-1，4，8，20，9，7 }，则该趟增量为：4.
5、冒泡排序
6、快速排序
7、直接插入排序
8、简单选择排序
9、希尔排序的步分结果
