数据结构排序

在数据结构中，排序有以下几种分类：

（1）按存储位置分为内部排序和外部排序； （2）按排序算法或者逻辑分为插入排序、选择排序、交换排序、归并排序和基数排序； （3）按排序结果分为升序和降序。

说到排序就可以说到稳定性。稳定性我们可以理解为：在待排序数字中的重复数据，在排序前后的相对前后位置不变。 其中， 稳定的有：直接插入排序、冒泡排序、归并排序、基数排序 不稳定的有：Shell排序、选择排序（直接选择排序、堆排序）、快速排序

直接插入排序

代码实现

#include<stdio.h> void InsertSort(int *arr, int len) { int i; int j; for (i=2;i<len;i++) { arr[0] = arr[i]; for (j=i-1;arr[j]>arr[0];j--) { arr[j + 1] = arr[j]; } arr[j + 1] = arr[0]; } }

时间复杂度 ：O(n^2) 空间复杂度：O(1)

代码测试

int main() { int arr[] = { -1,55,1,3,11,5,8,6,25,14,47}; int len = sizeof(arr) / sizeof(arr[0]); InsertSort(arr, len); return 0; }

Shell（希尔）排序

代码实现

#include<stdio.h> void Shell(int *arr, int len,int dk) { int i; int j; int tmp; for (i=dk;i<len;i++) { tmp = arr[i]; for (j=i-dk;j>=0 && arr[j]>tmp;j=j-dk) { arr[j + dk] = arr[j]; } arr[j + dk] = tmp; } } void shellSort(int *arr,int arr_len,int *dka,int dka_len) { for (int i=0;i<dka_len;i++) { Shell(arr,arr_len,dka[i]); } }

时间复杂度 ：O(n^2) 空间复杂度：O(1)

函数测试

int main() { int arr[] = { 55, 2, 44, 6, 8, 32, 46, 4, 26}; int dka[] = {5,3,1}; int arr_len = sizeof(arr) / sizeof(arr[0]); int dka_len = sizeof(dka) / sizeof(dka[0]); ShellSort(arr, arr_len, dka, dka_len); return 0; }

选择排序： ①简单选择排序 ②堆排序

①代码实现

#include<stdio.h> void SelectSort(int *arr, int len) { int i; int j; int min; int tmp; for (int i=0;i<len-1;i++) { min = i; for (j=i+1;j<len;j++) { if (arr[j] < arr[min]) { min = j; } } tmp = arr[min]; arr[min] = arr[i]; arr[i] = tmp; } }

时间复杂度 ：O(n^2) 空间复杂度：O(1)

函数测试

int main() { int arr[] = {1,5,6,8,6,5,85,9,6,1}; int len = sizeof(arr) / sizeof(arr[0]); SelectSort(arr, len); return 0; }

②堆排序

大根堆（升序）：父节点的数据大于子节点的数据。 父节点找子节点：i=1， 左子树 j=2*i，右子树j=2*i=1 子节点找父节点：j=5，i=j/2 小根堆：降序

代码测试

#include<stdio.h> /*找到最后一个有子节点的父节点：len/2；找到较大的子节点数与父节点上的数据比较，如果子节点上的数大于父节点的，那么将两者数据交换；调整完一遍之后将最顶端的数字与最后一个数字交换，最后一个数字不用再进入比较*/ void HeapAdjust(int *arr, int i, int len) { int j; //j <= len 有左子树 for (j=2*i;j<=len;j=2*j) { if (j<len && arr[j]<arr[j + 1]) { j++; } if (arr[j] < arr[i]) { break; } arr[0] = arr[i]; arr[i] = arr[j]; arr[j] = arr[0]; i = j; } } void HeapSort(int *arr, int len) { int tmp; for (int i=len/2;i>0;i--) { HeapAdjust(arr,i,len); } for (int j=len;j>0;j--) { tmp = arr[1]; arr[1] = arr[j]; arr[j] = tmp; HeapAdjust(arr,1,j-1); } }

时间复杂度 ：O(log2n) 空间复杂度：O(1)

函数测试

int main() { int arr[] = {516,8,154,8,44,52,821,56,42}; int arr1[] = {215,48,20,8,632,8,865,1}; int len = sizeof(arr)/sizeof(arr[0]) -1; HeapSort(arr,len); return 0; }

交换排序： ①冒泡排序 ②快速排序

①代码实现

#include<stdio.h> void BubbleSort(int *arr,int len) { int tmp; bool mark = false; for (int i=0;i<len-1;i++) { mark = false; for (int j=0;j<len-1-i;j++) { if (arr[j]>arr[j+1]) { tmp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = tmp; mark = true; } } printf("i = %d\n",i); if (!mark) { break; } } }

时间复杂度 ：O(n^2) 空间复杂度：O(1)

代码测试

int main() { int arr[] = {8,651,686,51,52,64,65,85,16,516}; int len = sizeof(arr) / sizeof(arr[0]); BubbleSort(arr, len); return 0; }

②代码实现

int Partition(int *arr,int low,int high) { int tmp = arr[low]; while(low < high) { while (low < high && arr[high] >= tmp)high--; arr[low] = arr[high]; while (low < high && arr[low] <= tmp)low++; arr[high] = arr[low]; } arr[low] = tmp; return low; } void QSort(int *arr,int low,int high) { if (low < high) { int boundKey = Partition(arr,low, high); QSort(arr, low, boundKey - 1); QSort(arr, boundKey+1, high); } } void QuickSort(int *arr,int len) { QSort(arr,0,len-1); }

时间复杂度 ：O(n^2) 空间复杂度：O(nlog2n)

代码测试

int main() { int arr[] = {65，46，548，68，19，5，6，56，569}; int len = sizeof(arr) / sizeof(arr[0]); QuickSort(arr,len); printf("\n"); return 0; }

归并排序

代码实现

#include<stdio.h> void Merge(int *arr,int *tmp,int StartIndex,int MidIndex,int EndIndex) { int i = StartIndex; int j = MidIndex + 1; int k = StartIndex; while (i != MidIndex + 1 && j != EndIndex + 1) { if (arr[i] > arr[j]) { tmp[k++] = arr[j++]; } else { tmp[k++] = arr[i++]; } } while (i != MidIndex + 1) { tmp[k++] = arr[i++]; } while (j != EndIndex + 1) { tmp[k++] = arr[j++]; } for (int i=StartIndex;i <= EndIndex; i++) { arr[i] = tmp[i]; } } void MergeSort(int *arr,int *tmp,int StartIndex,int EndIndex) { if (StartIndex < EndIndex) { int MidIndex = (StartIndex + EndIndex) / 2; MergeSort(arr,tmp,StartIndex,MidIndex); MergeSort(arr,tmp,MidIndex + 1,EndIndex); Merge(arr,tmp,StartIndex,MidIndex,EndIndex); } }

时间复杂度 ：O(nlog2n) 空间复杂度：O(n)

代码测试

#define N 12 int main() { int arr[12] = {2,85,1,65,6,16,32,15,88,964,53,4}; int len = sizeof(arr) / sizeof(arr[0]); int tmp[N]; MergeSort(arr,tmp,0,len-1); return 0; }

基数排序

将待排序数列分别根据个位、十位、百位排序：

代码实现

#include<stdio.h> #include<math.h> #define N 14 int FindMaxFinger(int *arr, int len)//找到最大数是几位数 { int max = arr[0]; for (int i=1;i<len;i++) { if (arr[i] > max) { max = arr[i]; } } int count = 0; while(max != 0) { max = max/10; count++; } return count; } //每个数据分别在个、十、百位上的数 int FindFingerNumber(int num, int fin) { return num/(int)pow(10.0,fin) % 10; } void Radix(int *arr, int len, int fin) { int tmp[10][N] = {}; int num_fin; int count[10] = {}; for (int i=0;i<len;i++) { num_fin = FindFingerNumber(arr[i],fin); tmp[num_fin][count[num_fin]] = arr[i]; count[num_fin]++; } int index = 0; for (int i=0;i<10;i++) { for (int j=0;j<count[i];j++) { arr[index++] = tmp[i][j]; } } } void RadixSort(int *arr, int len) { int MaxFinNum = FindMaxFinger(arr,len); for (int i=0;i<MaxFinNum;i++) { Radix(arr,len,i); } }

时间复杂度 ：O(d(r+n)) 空间复杂度：O(rd+n)

代码测试

int main() { int arr[N] = {5，51，3，541，351，56，5165，1，651}; int len = N; RadixSort(arr,len); return 0; }

链表排序

代码实现

#include<stdio.h> #include<stdlib.h> typedef struct Node { int val; //有效数据长度 Node* pNext; }Node; void Init(Node **head) { *head = (Node*)malloc(sizeof(Node)); if (*head == NULL)exit(0); (*head)->pNext = NULL; (*head)->val = 0; } void Insert(Node *head, int data) { Node* pCur = head; for (int i=0;i < head->val;i++) { pCur = pCur->pNext; } Node *NewNode = (Node*)malloc(sizeof(Node)); if (NewNode != NULL) { pCur->pNext = NewNode; NewNode->pNext = NULL; NewNode->val = data; head->val++; } } void Show(Node *head) { Node *pCur = head->pNext; for (int i=0;i<head->val;i++) { printf("%d ", pCur->val); pCur = pCur->pNext; } printf("\n"); } void ListSort(Node* head) { Node* pCur; Node* pAfter; for (int i = 0; i < head->val - 1; ++i) { pCur = head->pNext; pAfter = pCur->pNext; for (int j = 1; j < head->val - i; ++j) { if (pCur->val > pAfter->val) { int tmp = pCur->val; pCur->val = pAfter->val; pAfter->val = tmp; } pCur = pCur->pNext; pAfter = pAfter->pNext; } } }

代码测试

int main() { Node* pHead; Init(&pHead); for (int i=0;i<15;i++) { Insert(pHead, rand() % 100); } ListSort(pHead); Show(pHead); return 0; }