所有常用简单排序算法的c++代码
快速排序：void QuickSort(int s[],int l,int r) { if (l< r) { int i = l,j = r,x = s[l]; while (i < j) { while(i < j && s[j]>= x) // 从右向左找第一个小于x的数 j--; if(i < j) s[i++] = s[j]; while(i < j && s[i]< x) // 从左向右找第一个大于等于x的数 i++; if(i < j) s[j--] = s[i]; } s[i] = x; quickSort(s,l,i - 1); // 递归调用 quickSort(s,i + 1,r); } } 选择排序：void SelectSort(int s[],int n) { int i,j,k; for (i=0; i < n-1; i++) { k = i; for (j=i+1; j < n; j++) { if (a[j] < a[k]) k = j; } if (k != i) swap(s[k],s[i]); } } 冒泡排序：void BubbleSort(int s[],int n) { for (int i = 0; i < n; i++) { for (int j = 0; j < n - i - 1; j++) { if (s[j] > s[j + 1]) { swap(s[j],s[j + 1]); } } } } 希尔排序：void ShellSort(int s[],int n) { int gap; //gap为增量，为任意小于n的数 for(gap = 3; gap >0; gap--) { for(int i=0; i { for(int j = i+gap; j { int temp = s[j],k = j-gap; while(k>=0&&s[k]>temp) { s[k+gap] = s[k]; k = k-gap; } s[k+gap] = temp; } } } } void InsertSort(int s[],int n) { for (int i = 1; i < n; i++) //默认第一个元素已经是有序的，因此从第二个元素开始 { int j = i-1,temp=s[i]; while (j >=0&&s[j] > temp) //前一个元素比待插元素大 { s[j+1] = s[j]; //如果待插入元素比拍好元素大，则循环右移大的那部分元素 //留出位置给待插元素 j--; } s[j+1] = temp; //插入元素 } } /*该函数将数组下标范围[l1,r1]和[l2,r2]的有序序列合并成一个有序序列*/ void merge(int nums[],int l1,int r1,int l2,int r2 ) { int i = l1; //左半部分起始位置 int j = l2; //右半部分起始位置 int n = (r1 - l1 + 1) + (r2 - l2 + 1); //要合并的元素个数 vector int k = 0; //辅助数组其起始位置 while (i <= r1&&j <= r2) { //挑选两部分中最小的元素放入辅助数组中 if (nums[i] < nums[j]) temp[k++] = nums[i++]; else temp[k++] = nums[j++]; } //如果还有剩余，直接放入到辅助数组中 while (i <= r1) temp[k++] = nums[i++]; while (j <= r2) temp[k++] = nums[j++]; //更新原始数组元素 for (int i = 0; i < n;i++) { nums[l1 + i] = temp[i]; } } /*二路归并排序（递归实现）*/ void MergeSort(int nums[],int start,int end) { if (start < end) { int mid = (start + end)/2; //分割序列 MergeSort(nums,start,mid); //对序列左半部分进行归并排序 MergeSort(nums,mid + 1,end); //对序列右半部分进行归并排序 merge(nums,mid,end); //合并已经有序的两个序列 } } ?堆排序：void adjust(int arr[],int len,int index) { int left = 2 * index + 1; int right = 2 * index + 2; int maxIdx = index; if (left if (right if (maxIdx != index) // 如果maxIdx的值有更新 { swap(arr[maxIdx],arr[index]); adjust(arr,len,maxIdx);// 递归调整其他不满足堆性质的部分 } } void heapSort(int arr[],int size) { for (int i = size / 2 - 1; i >= 0; i--) // 对每一个非叶结点进行堆调整(从最后一个非叶结点开始) { adjust(arr,size,i); } for (int i = size - 1; i >= 1; i--) { swap(arr[0],arr[i]); // 将当前最大的放置到数组末尾 adjust(arr,i,0); // 将未完成排序的部分继续进行堆排序 } } （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |