广州网站建设gzqiyi,中国最好的少儿编程培训机构,深圳建设网站公司排名,做网站公司需要什么文章目录 一、冒泡排序代码实现 二、直接插入排序代码实现 三、希尔排序代码实现 四、选择排序代码实现 五、堆排序代码实现 六、快速排序代码实现 七、归并排序代码实现 八、计数排序代码实现 稳定性#xff1a;相同的数据排序后#xff0c;相对位置是否发生改变
一、冒泡排… 文章目录 一、冒泡排序代码实现 二、直接插入排序代码实现 三、希尔排序代码实现 四、选择排序代码实现 五、堆排序代码实现 六、快速排序代码实现 七、归并排序代码实现 八、计数排序代码实现 稳定性相同的数据排序后相对位置是否发生改变
一、冒泡排序 时间复杂度O(N^2) 空间复杂度O(1) 稳定性稳定 代码实现
void Swap(int* a, int* b)
{int tmp;tmp *a;*a *b;*b tmp;
}
void BubbleSort(int* a, int n)
{for (int j 0; j n; j){int exchange 0;for (size_t i 1; i n-j; i)if (a[i - 1] a[i]){Swap(a[i - 1], a[i]);exchange 1;}if (exchange 0){break;}}
}二、直接插入排序 时间复杂度O(N^2) 空间复杂度O(1) 稳定性稳定 代码实现
void InsertSort(int* a, int n)
{for (int i 0; i n; i){int end i;int tmp a[end 1];while (end0){if (tmp a[end])a[end 1] a[end];elsebreak;--end;}a[end 1] tmp;}
}三、希尔排序 时间复杂度O(N^1.3) 空间复杂度O(1) 稳定性不稳定 代码实现
void ShellSort(int* a, int n)
{int gap n;while (gap 1){gap gap / 3 1;for (int i 0; i n - gap; i){int end i;int tmp a[end gap];while (end 0){if (tmp a[end]){a[end gap] a[end];end - gap;}elsebreak;}a[end gap] tmp;}}
}四、选择排序 时间复杂度O(N^2) 空间复杂度O(1) 稳定性不稳定 代码实现
void SelectSort(int* a, int n)
{int begin 0;int end n - 1;while (begin end){int max begin, min begin;for (int i begin1; i end; i){if (a[i] a[max])max i;if (a[i] a[min])min i;}Swap(a[begin], a[min]);if (max begin)max min;Swap(a[end], a[max]);--end;begin;}
}五、堆排序 时间复杂度O(N*logN) 空间复杂度O(1) 稳定性不稳定 代码实现
void AdjustDown(int* a, int n, int parent)
{int child parent * 2 1;while (child n){if (child 1 n a[child 1] a[child]){child;}if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}
}void HeapSort(int* a, int n)
{for (int i (n - 1 - 1) / 2; i 0; i--){AdjustDown(a, n, i);}int end n - 1;while (end 0){Swap(a[0], a[end]);AdjustDown(a, end, 0);--end;}
}六、快速排序 时间复杂度O(N*logN) 空间复杂度O(logN) 稳定性不稳定 代码实现
//三数取中
int GetMidi(int* a, int left, int right)
{int midi (left right) / 2;if (a[left] a[midi]){if (a[midi] a[right])return midi;else if (a[right] a[left])return left;elsereturn right;}else{if (a[left] a[right])return left;else if (a[right] a[midi])return midi;elsereturn right;}
}
//hoare
int PartSort1(int* a, int left,int right)
{int keyP left;//GetMidi(a,left,right);while (left right){while (a[right] a[keyP] left right)--right;while (a[left] a[keyP] left right)left;Swap(a[left], a[right]);}Swap(a[keyP], a[left]);return left;
}
//挖坑法
int PartSort2(int* a, int left, int right)
{int midi GetMidi(a, left, right);Swap(a[left], a[midi]);int keyP a[left];//int keyP left;int hole left;while (left right){while (a[right] keyP left right)--right;a[hole] a[right];hole right;while (a[left] keyP left right)left;a[hole] a[left];hole left;}a[hole] keyP;return hole;
}
//前后指针
int PartSort3(int* a, int left, int right)
{int prev left;int cur prev 1;int keyP left;while (cur right){if (a[cur] a[keyP] prev ! cur){Swap(a[prev], a[cur]);}cur;}Swap(a[prev], a[keyP]);return prev;
}void QuickSort(int* a, int begin, int end)
{if (begin end)return;int key PartSort1(a, begin, end);QuickSort(a, begin, key - 1);QuickSort(a, key 1, end);
}void QuickSort1(int* a, int begin, int end)
{if (begin end)return;//小区间优化,小区间不在递归分割排序降低递归次数if ((end - begin 1) 10){int key PartSort1(a, begin, end);QuickSort1(a, begin, key - 1);QuickSort1(a, key 1, end);}else{InsertSort(a begin, end - begin 1);}
}void QuickSortNonR(int* a, int begin, int end)//非递归
{Stack st;StackInit(st);StackPush(st, end);StackPush(st, begin);while (!StackEmpty(st)){int left StackTop(st);StackPop(st);int right StackTop(st);StackPop(st);int key PartSort3(a, left, right);if (key 1 right){StackPush(st, right);StackPush(st, key 1);}if (begin key - 1){StackPush(st, key - 1);StackPush(st, begin);}}StackDestory(st);
}其中包含了三数取中基准值快排的三种实现方法hoare挖坑法前后指针及非递归方法 七、归并排序 时间复杂度O(N*logN) 空间复杂度O(N) 稳定性稳定 代码实现
void PartMergeSort(int* a, int* tmp, int begin, int end)
{if (end begin)return;int mid (begin end) / 2;PartMergeSort(a, tmp, begin, mid);PartMergeSort(a, tmp, mid 1, end);int begin1 begin, end1 mid;int begin2 mid 1, end2 end;int count begin;while (begin1 end1 begin2 end2){if (a[begin1] a[begin2])tmp[count] a[begin1];elsetmp[count] a[begin2];}while (begin1 end1){tmp[count] a[begin1];}while (begin2 end2){tmp[count] a[begin2];}memcpy(a begin, tmp begin, (end - begin 1) * sizeof(int));
}void MergeSort(int* a, int n)
{int* tmp malloc(sizeof(int) * n);if (tmp NULL){perror(malloc fail);exit(-1);}PartMergeSort(a, tmp, 0, n - 1);free(tmp);
}void MergeSortNonR(int* a, int n)
{int* tmp malloc(sizeof(int) * n);if (tmp NULL){perror(malloc fail);exit(-1);}int gap 1;while (gap n){for (int i 0; i n; i 2 * gap){int begin1 i, end1 i gap - 1;int begin2 i gap, end2 i 2 * gap - 1;int count i;if (begin2 n)break;if (end2 n)end2 n - 1;while (begin1 end1 begin2 end2){if (a[begin1] a[begin2])tmp[count] a[begin1];elsetmp[count] a[begin2];}while (begin1 end1){tmp[count] a[begin1];}while (begin2 end2){tmp[count] a[begin2];}memcpy(a i, tmp i, (end2-i1) * sizeof(int));} gap * 2;}
}其中包含了递归及非递归实现方法 八、计数排序 时间复杂度O(Nrange) 空间复杂度O(range) 代码实现
void CountSort(int* a, int n)
{int min a[0], max a[0];for (size_t i 0; i n; i){if (a[i] min)min a[i];if (a[i] max)max a[i];}int range max - min 1;int* count (int*)malloc(sizeof(int) * range);printf(\nrange:%d\n, range);if (count NULL){perror(malloc fail);return;}memset(count, 0, sizeof(int) * range);// 统计数据出现次数for (int i 0; i n; i){count[a[i] - min];}// 排序int j 0;for (int i 0; i range; i){while (count[i]--){a[j] i min;}}
}
