奇偶排序又叫奇偶换位排序,是通过比较数组中相邻位置(奇-偶)的两个元素,如果奇偶对第一个大于第二个,则交换,重复该操作。然后,用类似的方式,依次比对所有偶奇对的元素。下面给出奇偶排序的实现代码:
1、奇偶排序头文件:oddEvenSort.h
#ifndef ODDEVENSORT_H
#define ODDEVENSORT_H
#include<stdbool.h>
extern void oddEvenSort(int *pArr, const int length);
#endif
2、奇偶排序源文件:oddEvenSort.c
#include "oddEvenSort.h"
void oddEvenSort(int *pArr, const int length)
{
int i, tmp;
bool sorted =false;
while(!sorted)
{
sorted=true;
for(i=1; i<length-1; i+=2)
{
if(*(pArr+i)>*(pArr+i+1))
{
sorted=false;
tmp=*(pArr+i);
*(pArr+i)=*(pArr+i+1);
*(pArr+i+1)=tmp;
}
}
for(i=0; i<length-1; i+=2)
{
if(*(pArr+i)>*(pArr+i+1))
{
sorted=false;
tmp=*(pArr+i);
*(pArr+i)=*(pArr+i+1);
*(pArr+i+1)=tmp;
}
}
}
}
3、main头文件:main.h
#ifndef MAIN_H
#define MAIN_H
#include<stdio.h>
#include "oddEvenSort.h"
int main(void);
void initRandomArr(int *pArr, const int length);
void showArr(const int *pArr, const int length);
#endif
4、main源文件:main.c
#include "main.h"
int main(void)
{
int length;
printf("Input array length:\n");
scanf("%d", &length);
if(length < 0)
{
printf("Array length must be larger 0\n");
return 1;
}
int arr[length];
initRandomArr(arr, length);
printf("Get random array:\n");
showArr(arr, length);
oddEvenSort(arr, length);
printf("oddEventSort result:\n");
showArr(arr, length);
return 0;
}
void initRandomArr(int * pArr, const int length)
{
srand(time(NULL));
int i;
for(i=0; i<length; i++)
{
*(pArr+i)=rand()%1000;
}
}
void showArr(const int *pArr, const int length)
{
int i;
for(i=0; i< length; i++)
{
printf("%d ", *(pArr+i));
}
printf("\n");
}
5、编译
[root@localhost oddEvenSort]$ gcc -c oddEvenSort.c
[root@localhost oddEvenSort]$ gcc -c main.c
[root@localhost oddEvenSort]$ gcc -o main main.o oddEvenSort.o
执行可执行文件main如下:
[root@localhost oddEvenSort]$ ./main
Input array length:
6
Get random array:
59 967 202 868 171 869
oddEventSort result:
59 171 202 868 869 967
奇偶排序最差时间复杂度是O(n²),适用于排序小列表