Dowemo
0 0 0 0

In data structures, sorting has several categories:

( 1 ) divided into internal sorting and external sorting by storage location;
( 2 ) according to the sorting algorithm or logic divided into row order, select sorting, exchange sorting, merging sort and base number sequence;
( 3 ) by sorting results into ascending and descending order.

It says that the sort can be said to be stable. Stability we can understand as: Repeat data in the number of numbers to be sorted and change before and after sorting.
And,
Stable: directly inserted into the order, bubble, merge sort, base number sequence sequence.
Unstable: shell sorting, selection sort ( direct selection sort, heap sequence ), fast sorting

Directly inserted into the order.

Code implementation

#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];
 }
}

Time complexity: o ( n^2 )
Space complexity: o ( 1 )

Code test

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);
 return0;
}

Shell ( hill ) sort

Code implementation

#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]);
 }
}

Time complexity: o ( n^2 )
Space complexity: o ( 1 )

Function test

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);
 return0;
}

Select sort:
Simple selection sort
② sequencing

Code implementation

#include<stdio.h>void SelectSort(int *arr, int len)
{
 int i;
 int j;
 intmin;
 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;
 }
}

Time complexity: o ( n^2 )
Space complexity: o ( 1 )

Function test

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

② sequencing
这里写图片描述

Large root heap ( ascending ): The data of the parent node is greater than the data of the child node.
Pare not nodes find child nodes: I = 1, left subtree j = 2 * I, right subtree j = 2 * I = 1
Child nodes find the pare not node: J = 5, I = j/2
Small root heap: descending

Code test

#include<stdio.h>/*找到最后一个有子节点的父节点:len/2;找到较大的子节点数与父节点上的数据比较,如果子节点上的数大于父节点的,那么将两者数据交换;调整完一遍之后将最顶端的数字与最后一个数字交换,最后一个数字不用再进入比较*/void HeapAdjust(int *arr, int i, intlen)
{
 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, intlen)
{
 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);
 }
}

Time complexity: o ( log2n )
Space complexity: o ( 1 )

Function test

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);
 return0;
}

Exchange sort:
①.
Fast sorting

Code implementation

#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 = %dn",i);
 if (!mark)
 {
 break;
 }
 }
}

Time complexity: o ( n^2 )
Space complexity: o ( 1 )

Code test

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

Code implementation

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);
}

Time complexity: o ( n^2 )
Space complexity: o ( nlog2n )

Code test

int main()
{
 int arr[] = {654654868195656569};
 int len = sizeof(arr)/sizeof(arr[0]);
 QuickSort(arr,len);
 printf("n");
 return0;
}

Merging sort

这里写图片描述

Code implementation

#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);
 }
}

Time complexity: o ( nlog2n )
Space complexity: o ( n )

Code test

#define N 12int 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);
 return0;
}

sequence

Sort the sorted sequence according to the bits, 10, and hundreds:
将待排序数列分别根据个位、十位、百位排序。

Code implementation

#include<stdio.h>#include<math.h>#define N 14int FindMaxFinger(int *arr, int len)//找到最大数是几位数{
 int max = arr[0];
 for (int i=1;i<len;i++)
 {
 if (arr[i]> max)
 {
 max = arr[i];
 }
 }
 intcount = 0;
 while(max!= 0)
 {
 max = max/10;
 count++;
 }
 returncount;
}//每个数据分别在个、十、百位上的数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;
 intcount[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]++;
 }
 intindex = 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);
 }
}

Time complexity: o ( R + n )
Space complexity: o ( rd + n )

Code test

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

List sorting

Code implementation

#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;
 }
 }
}

Code test

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



Copyright © 2011 Dowemo All rights reserved.    Creative Commons   AboutUs