// sort_algorituhm.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。 // #include <iostream> #include<algorithm> using namespace std; #define elemtype int //冒泡排序法,组个遍历,大数往后,每次都是"完全遍历",从0开始 void sort_bubbling(elemtype *p, int sort_len) { elemtype temp = 0; int i, j; for(i=0; i < (sort_len-1);i++) for (j = 0; j < (sort_len - 1 - i); j++) { if (p[j] > p[j + 1]) { temp = p[j]; p[j] = p[j + 1]; p[j + 1] = temp; } } } //选择最大的值放在序列最后,重点:记录当前轮询周期下数列最值下标,找出后直接与数列尾端交换 //每次比较后,因为已经找出了最大值放到最后,下一次数列比较只到最值之前一个数即可 void sort_select(elemtype* p, int sort_len) { elemtype temp = p[0]; // elemtype Min_num = p[0]; int index = 0; int i,j; for (j = 0; j < (sort_len-1); j++) { for (i = 0; i < (sort_len-j); i++) { if (p[i] > temp) { temp = p[i]; index = i; } } temp = p[sort_len-j-1]; p[sort_len-j-1] = p[index]; p[index] = temp; index = 0; temp = p[index]; } } //插入排序法,重点:记录当前正在比较的数组元素下标,逐次之前的元素比较交换位置,直达插入完成 void sort_insert(elemtype* p, int sort_len) { int i, j, key; for (i = 1; i < sort_len; i++) { key = p[i]; j = i - 1; while ((j >= 0) && (p[j] > key)) { p[j + 1] = p[j]; j--; } p[j + 1] = key; } } //希尔排序算法 void sort_shell(elemtype* p, int sort_len) { int gap, i, j; int temp; for (gap = sort_len >> 1; gap > 0; gap >>= 1) //获得每次的分隔数 for (i = gap; i < sort_len; i++)//按照分隔数,将数组分割为多组分别进行插入排列,这里的i++使得不同分组的前几个数在下一个gap到来之前并行分别排序 { temp = p[i]; //插入排序法中,正在比较的数组元素 //按指定间隔遍历链表,寻找插入位置,因为for循环开始时,j = i - gap //使得分的小组数列从建立起就是升序排列,即插入排序法 for (j = i - gap; j >= 0 && p[j] > temp; j -= gap) p[j + gap] = p[j]; p[j + gap] = temp; } } elemtype min(elemtype x, elemtype y) { return y > x ? x : y; } //归并排序 ,迭代法,将数组向下分割为单个元素,再对单个元素进行多次归并 void merge_sort(int arr[], int len) { int* a = arr; int* b = (int*)malloc(len * sizeof(int)); int seg, start; for (seg = 1; seg < len; seg += seg) { for (start = 0; start < len; start += seg * 2) { //第一次归并,将数组排序为2个一组的(尾部单独算),升序排列的数列 //第二次归并,将排序好的2个一组的数列,小端比小端开始,依次比较组合为4个一组的(尾部单独算),升序排列的数组 // ............. //第n次归并,将len/2长度的两个排序好的数组,小端开始,,依次比较完成归并 int low = start, mid = min(start + seg, len), high = min(start + seg * 2, len); int k = low; int start1 = low, end1 = mid; int start2 = mid, end2 = high;//start1,start2为每次比较的有序数组的首地址 //下面三句完成两个升序数组的升序合并 while (start1 < end1 && start2 < end2) b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++]; while (start1 < end1) //因为是已经排序好的数列,小值已经比另一数列最大值大了,后面直接复制就行 b[k++] = a[start1++]; while (start2 < end2) b[k++] = a[start2++]; } int* temp = a; a = b; b = temp; } if (a != arr) { int i; for (i = 0; i < len; i++) b[i] = a[i]; b = a; } free(b); } //归并排序 递归法,将数组向下分割为单个元素,再对单个元素进行多次归并 void sort_merge_recursive(int* a, int* b,int start,int end) { if (start >= (end-1)) return; //start指向最后是,表示当前递归遍历完毕,开始返回 int seg = (end - start)/2; int low = start, mid = min(start + seg, end), high = end; int start1 = low, end1 = mid; int start2 = mid, end2 = high;//start1,start2为每次比较的有序数组的首地址 sort_merge_recursive(a, b, start1, end1); sort_merge_recursive(a, b, start2, end2); int k = start; int i = 0; //下面三句完成两个升序数组的升序合并 while (start1 < end1 && start2 < end2) b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++]; while (start1 < end1) //因为是已经排序好的数列,小值已经比另一数列最大值大了,后面直接复制就行 b[k++] = a[start1++]; while (start2 < end2) b[k++] = a[start2++]; for (i = start;i<end;i++) { a[i] = b[i]; } } void sort_My_merge_recursive(int arr[], int len) { int* b = (int*)malloc(len * sizeof(int)); sort_merge_recursive(arr, b,0,len); free(b); } //快速排序,迭代法 typedef struct _Range {//用于记录当前分区起点与终点 int start, end; }Range; Range new_Range(int s, int e) { Range r = {0,0}; r.start = s; r.end = e; return r; } void swap(int *x,int *y) { int t = *x; *x = *y; *y = t; } void sort_quick(int arr[], const int len) { if (len <= 0) return; // 避免len等於負值時引發段錯誤(Segment Fault) Range* r = (Range*)malloc(sizeof(Range) * len); // r[]模擬列表,p為數量,r[p++]為push,r[--p]為pop且取得元素 if (r == NULL) return; int ptop = 0; r[ptop++] = new_Range(0, len - 1); while (ptop) { Range range = r[--ptop]; if (range.start >= range.end) continue; int mid = arr[(range.start + range.end) / 2];// 選取中間點為基準點 int left = range.start, right = range.end; do { while (arr[left] < mid) left++; while (arr[right] > mid) right--; if (left <= right) { swap(&arr[left],&arr[right]); left++; right--; //移动指针以继续 } } while (left <= right); if(range.start<right) r[ptop++] = new_Range(range.start, right); if(range.end> left) r[ptop++] = new_Range(left, range.end); } } //快速排序,递归法 void sort_quick_rcursive(int arr[],int start,int end) { if (start >= end)return; int left = start, right = end; int mid = arr[(start + end) / 2]; do { while (arr[left] < mid) left++; while (arr[right] > mid) right--; if (left <= right) { swap(&arr[left], &arr[right]); left++; right--; //移动指针以继续 } } while (left <= right); sort_quick_rcursive(arr, start, right); sort_quick_rcursive(arr, left, end); } void sort_My_quick_rcursive(int arr[], int len) { sort_quick_rcursive(arr, 0, len - 1); } //堆排序 void my_heapify(int arr[],int dad_index,int len)//最大堆生成 { int son = dad_index * 2 + 1; while (len > son)//使用while遍历挂在该父节点之后所有节点,避免因为数值调换引起的最大堆出错 { if ((son + 1) < len && arr[son] < arr[son+1])//获取子节点中大值 { son++; } if (arr[dad_index] >= arr[son]) return; swap(&arr[dad_index],&arr[son]); dad_index = son; //父亲下标指向与之调换的儿子下标,进行以该儿子下标为父亲节点的最大堆生成,避免因为数值调换引起的最大堆出错(父节点值不是最大) son = dad_index * 2 + 1; } } void sort_heap(int arr[], int len) { int i, j; for (i = len / 2 + 1; i >= 0; i--) my_heapify(arr, i, len);//建立最大堆 for (i = len - 1; i > 0;i--)//在最大堆上操作 { swap(&arr[0],&arr[i]);//将当前最低节点(较上层较小)与max值交换 my_heapify(arr, 0,i-1);//从根节点0开始,交换后的小值不断向下沉淀,大值不断上浮,i-1是为排除有序数列 } } //计数排序,用于0~99内计数 void counting_sort(int* ini_arr, int* sorted_arr, int n) { int* count_arr = (int*)malloc(sizeof(int) * 100); int i, j, k; for (k = 0; k < 100; k++) //初始化count_arr,每个数据重复计数初始为0 count_arr[k] = 0; for (i = 0; i < n; i++) count_arr[ini_arr[i]]++;//直接在数据范围内对重复数据进行重复计数 for (k = 1; k < 100; k++)// count_arr[k] += count_arr[k - 1];//向后叠加计数值,后一个值储存全面所有值数量和,间接获得了每个值排序后的序号 for (j = n; j > 0; j--) sorted_arr[--count_arr[ini_arr[j - 1]]] = ini_arr[j - 1]; //填充每个数据到排序后数字应该到的位置 //count_arr[ini_arr[j - 1]]:当前数据应在地址,同时地址减一,应对数据重复情况,向后填充 free(count_arr); } //基数排序 void sort_radix(int* p, int len) { int* sorted_arr = (int*)malloc(sizeof(int) * len); int BASE = 10;//取余10 int exp = 1;//从1开始除,num/exp%BASE, 处理完一轮exp = exp*BASE 依次获得个位、十位... int max_num = p[0], i; for (i = 1; i < len; i++)//获取最大值,判断循环结束条件 { if (p[i] > max_num) max_num = p[i]; } while (max_num / exp >0) { int count_arr[10] = {0}; for (i = 0; i < len; i++) { count_arr[p[i] / exp % BASE]++;//直接在数据范围内对重复数据进行重复计数 } for (i = 1; i < len; i++) { count_arr[i] += count_arr[i - 1];//向后叠加计数值,后一个值储存全面所有值数量和,间接获得了每个值排序后的序号 } for (i = len-1; i >= 0; i--) { sorted_arr[--count_arr[p[i] / exp % BASE]] = p[i]; } for (i = 0; i < len; i++) { p[i] = sorted_arr[i]; } exp = exp * BASE; } } int main() { elemtype arr[] = { 12,32,34,13,64,234,7,2,5652,34 }; int loop = 0; int n = 10; sort_bubbling(arr,n);
for (; loop < n; loop++) { printf("%d ", arr[loop]); } printf("\n"); system("pause"); }
标签:sort,arr,语言,start,int,len,++,算法,排序 From: https://www.cnblogs.com/ysyyrps-hhl/p/17566749.html