奇偶排序又叫奇偶換位排序,是通過比較數組中相鄰位置(奇-偶)的兩個元素,如果奇偶對第一個大於第二個,則交換,重復該操作。然後,用類似的方式,依次比對所有偶奇對的元素。下面給出奇偶排序的實現代碼:
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²),適用於排序小列表