建设工程许可证在那个网站办,金融行业网站制作,陕西省网站备案,申请网站官网堆排序#xff1a;
在学习堆之后我们知道了大堆和小堆#xff0c;对于大堆而言第一个节点就是对大值#xff0c;对于小堆而言#xff0c;第一个值就是最小的值。如果我们把第一个值与最后一个值交换再对最后一个值前面的数据重新建堆#xff0c;如此下去就可以实现建堆排…堆排序
在学习堆之后我们知道了大堆和小堆对于大堆而言第一个节点就是对大值对于小堆而言第一个值就是最小的值。如果我们把第一个值与最后一个值交换再对最后一个值前面的数据重新建堆如此下去就可以实现建堆排序。
建堆的两种方法
向上调整建堆 向上调整建堆的思路是从第一个开始先后添加数据在每次到一个数据是如果比父节点大小就与父节点交换位置并继续向上调整。 算法复杂度O(N*logN) 向下调整建堆 因为对于大小堆来说它的左右子树也都应该是大小堆以此类推我们最小的数也应该是大小堆于是我们就从最小的树开始建堆。 算法复杂度O(N) 插入排序 直接插入排序是认为要插入数之前的所有数据已经排序好,用一个tmp临时变量存储要插入的值,如果要插入值的前一个数据比他大,那么就向后覆盖,接着继续往前比,直到遇到比要插入值小的数据,将要插入值插入在该数据的后一位。 希儿排序: 事实上就是插入排序的升级版对插入排序进行调整使数组趋于有序最后一次进行一次插入排序。
选择排序 选择排序是从数据的首端去进行选择,遍历一遍数组取选出最大值和最小值,选出后交换放在两端排序,继续去选择。注意的是如果最大值是第一个数据,后面交换时会出现数据被替代的情况,这种情 况下我们需要在交换后将最大值下标指向最小值下标。 快速排序
递归 非递归 归并排序
递归 非递归 计数排序
其思想就是利用一个数组数组名表示需要排序的数组里的数据其大小就是出现次数最后从大到小存在一个数组里。 #include SORT.hvoid swap(int* a, int* b)
{//printf(%d %d --, *a, *b);int tmp *a;*a *b;*b tmp;//printf(%d %d\n, *a, *b);
}/*******************************************************************************/
/*---------------------------------堆排序------------------------------------- */
/*******************************************************************************/
void heapSort_F(int* arr,int n)//向下调整建堆
{//升序建大堆int last_father (n - 1) / 2; //找到第一个父while (last_father ! -1){int father last_father;int child father * 2 1;while (child n){if (child 1 n arr[child 1] arr[child]) //找到最大的孩子{child;}if (arr[father] arr[child]) //孩子比父亲大就交换{int tmp arr[father];arr[father] arr[child];arr[child] tmp;}father child; //继续向下大的往上走作为父child father * 2 1;} //大堆好了--last_father;}while (n){//交换首尾巴size--int tmp arr[0];arr[0] arr[n];arr[n] tmp;--n;int father 0;int child father * 2 1;while (child n) //向下找大的作为父{if (child 1 n){if (arr[child 1] arr[child])child;}if (arr[father] arr[child]){int tmp arr[father];arr[father] arr[child];arr[child] tmp;}father child;child father * 2 1;}}
}void heapSort_S(int* arr, int n)//向上调整建堆
{//降序建小堆for (int i 1; i n; i) //从前往后插入每插入一个判断上面的父是否需要向上改变{int child n;while (child){int father (child - 1) / 2;if (arr[father] arr[child]){int tmp arr[child];arr[child] arr[father];arr[father] tmp;}child father;}}while (n){int tmp arr[0];arr[0] arr[n];arr[n] tmp;--n;int father 0;int child father * 2 1;while (child n){if (child 1 n){if (arr[child 1] arr[child])child;}if (arr[father] arr[child]){int tmp arr[father];arr[father] arr[child];arr[child] tmp;}father child;child father * 2 1;}}
}
/**/
/**//*******************************************************************************/
/*--------------------------------插入排序------------------------------------ */
/*******************************************************************************/
void InsertSort(int* arr, int n)
{int end 0;while (end ! n - 1){end;int val arr[end];int change end;while (change ! 0){if (arr[change - 1] val){arr[change] arr[change - 1];--change;}else break;}arr[change] val;}
}
//void InsertSort(int* a, int n)
//{
// // [0, n-1]
// for (int i 0; i n - 1; i)
// {
// // [0, n-2]是最后一组
// // [0,end]有序 end1位置的值插入[0,end]保持有序
// int end i;
// int tmp a[end 1];
// while (end 0)
// {
// if (tmp a[end])
// {
// a[end 1] a[end];
// --end;
// }
// else
// {
// break;
// }
// }
// a[end 1] tmp;
// }
//}
//
/**/
/**//*******************************************************************************/
/*--------------------------------希儿排序------------------------------------ */
/*******************************************************************************/
void ShellSort(int* arr, int n)
{int gap n;while(gap1){gap gap / 3 1;//for (size_t j0; j gap; j)//{// for (size_t i j; i n-gap; igap) //一组一组for (size_t i 0; i n - gap; i) //多组并着走{int end i;int tmp arr[end gap];while (end 0){if (tmp arr[end]){arr[end gap] arr[end];end - gap;}else{break;}}arr[end gap] tmp;}//}}
}
/**/
/**//*******************************************************************************/
/*------------------------------ 选择排序 ---------------------------------- */
/*******************************************************************************/
void SelectSort(int* arr, int n)
{int start 0; int end n - 1;while (start end){int mini start;int maxi end;for (int i start; i end; i){if (arr[i] arr[mini])mini i;if (arr[i] arr[maxi])maxi i;}swap(arr[start], arr[mini]);if (start maxi){maxi mini;}swap(arr[end], arr[maxi]);start;--end;}
}
/**/
/**//*******************************************************************************/
/*--------------------------------快速排序------------------------------------ */
/*******************************************************************************/
int get_midi(int* arr, int left, int right) //优化--三值取中
{int midi (left right) / 2;if (arr[midi] arr[left]){if (arr[midi] arr[right])return midi;else{if (arr[left] arr[right])return left;else return right;}}else{if (arr[midi] arr[right])return midi;else{if (arr[left] arr[right])return left;else return right;}}
}
// 霍尔版
int partSort1(int* arr, int left, int right)
{if (right - left 10)//小区间优化{InsertSort(arr[left], right - left 1);}int midi get_midi(arr, left, right);int keyi left;swap(arr[midi], arr[keyi]);int key arr[left];int begin left, end right;while (begin end){//向右找小while (arr[end] key begin end){--end;}//向左找大while (arr[begin] key begin end){begin;}swap(arr[begin], arr[end]);}swap(arr[keyi], arr[end]);return begin;
}
// 双指针
int partSort2(int* arr, int left, int right)
{int keyi left;int key arr[left];int prev left;int cur prev 1;while (curright){if (arr[cur] key prev ! cur)swap(arr[cur], arr[prev]);cur;}swap(arr[prev], arr[keyi]);return prev;
}void QuickSort(int* arr, int left, int right)
{if (left right)return;else{int begin partSort2(arr, left, right); //双指针//int begin partSort1(arr, left, right); //霍尔版QuickSort(arr, left, begin - 1);QuickSort(arr, begin 1, right);}}
/**/
/**//*******************************************************************************/
/*---------------------------快速排序非递归------------------------------- */
/*******************************************************************************/
void quickSortNonR(int* arr, int left, int right)
{ST st;STinit(st);STpush(st, left);STpush(st, right);while (!STEmpty(st)){int end STtop(st);STpop(st);int begin STtop(st);STpop(st);int mid partSort1(arr, begin, end);if (mid - 1 begin){STpush(st, begin);STpush(st, mid - 1);}if (mid 1 end){STpush(st, mid 1);STpush(st, end);}}
}
/**/
/**//*******************************************************************************/
/*--------------------------------归并排序------------------------------------ */
/*******************************************************************************/
void _mergeSort(int* arr, int* tmp, int begin, int end)
{if (begin end)return;int mid (begin end) / 2;_mergeSort(arr, tmp, begin, mid);_mergeSort(arr, tmp, mid 1, end);int begin1 begin, end1 mid;int begin2 mid 1, end2 end;int i begin;while (begin1 end1 begin2 end2){if (arr[begin1] arr[begin2]){tmp[i] arr[begin1];}else{tmp[i] arr[begin2];}}while (begin1 end1)tmp[i] arr[begin1];while (begin2 end2)tmp[i] arr[begin2];memcpy(arr begin, tmp begin, sizeof(int) * (end - begin 1));
}
void mergeSort(int* arr, int n)
{int* tmp (int*)malloc(sizeof(int) * n);_mergeSort(arr, tmp, 0, n-1);free(tmp);
}
/**/
/**//*******************************************************************************/
/*---------------------------归并排序非递归------------------------------- */
/*******************************************************************************/
void mergeSortNonR(int* arr, int n)
{int* tmp (int*)malloc(sizeof(int) * n);int gap 1;while (gap n){for (int i 0; i n; i gap * 2){int j i;int begin1 i, end1 i gap - 1;int begin2 i gap, end2 i 2 * gap - 1;if (begin2 n)break;if (end2 n)end2 n - 1;while (begin1 end1 begin2 end2){if (arr[begin1] arr[begin2]){tmp[j] arr[begin1];}else{tmp[j] arr[begin2];}}while (begin1 end1)tmp[j] arr[begin1];while (begin2 end2)tmp[j] arr[begin2];memcpy(arr i, tmp i, sizeof(int) * (end2 - i 1));}gap * 2;}free(tmp);
}
/**/
/**//*******************************************************************************/
/*--------------------------------计数排序------------------------------------ */
/*******************************************************************************/void count_Sort(int* arr, int sz)
{int max arr[0];int min arr[0];for (int i 0; i sz; i){if (arr[i] max)max arr[i];if (arr[i] min)min arr[i];}int* tmp (int*)calloc(max - min 1, sizeof(int));for (int i 0; i sz; i){tmp[arr[i] - min];}int i 0;for (int j 0; j max - min 1; j){while (tmp[j]--){arr[i] j min;}}
}/**/
/**/
