(排序算法拾掇)NEFU 30/32
(排序算法整理)NEFU 30/32
nefu 32
其实，在ACM比赛时，很少人会自己去写平常时的那种排序算法，都是直接使用库函数里面的排序算法。但是表示或者是面试的时候通常会问道这些基本的算法。所以今天就把排序算法发整理了一下。也在OJ上找了几道简单题来验证一下。
现在把其中基本的排序算法整理如下（暂时还没有将堆排序的实现贴上来）：
/*
* nefu_sort.cpp
*
* Created on: 2014年5月18日
* Author: pc
*/
#include <iostream>
#include <cstdio>
using namespace std;
int n;
/**
* 第一种交换算法:
* 借助中间变量
*/
void swap1(int arr[],int i,int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
/**
* 第二种交换算法:
* 不借助中间变量,使用算术运算
*/
void swap2(int arr[],int i, int j){
arr[i] = arr[i] + arr[j];
arr[j] = arr[i] - arr[j];
arr[i] = arr[i] - arr[j];
}
/**
* 第三种交换算法:
* 使用位运算
*/
void swap3(int arr[], int i, int j){
arr[i] = arr[i]^arr[j];
arr[j] = arr[i]^arr[j];
arr[i] = arr[i]^arr[j];
}
/**
* 冒泡排序的第一种方式:
* 标准方式
*/
void bubblesort1(int arr[],int n){
int i;
int j;
for(i = 0 ; i < n-1 ;++i){//循环n-1次(因为1个数默认为有序的状态),每次能是一个数达到有序状态
for(j = 0 ; j < n-i-1 ; ++j){//每次将从第一个数到有序状态之前的数进行比较(有序状态以后的数不再需要进行比较)
if(arr[j] > arr[j+1]){//如果前面的数大于后面的数
swap3(arr,j,j+1);//则进行交换
}
}
}
}
/**
* 冒泡排序的第二种方式:采用"扫描一遍以后,假如没有发生交换,即是达到了有序状态"的特点进行优化
*/
void bubblesort2(int arr[],int n){
int k = n;
bool flag = true;
while(flag){
flag = false;
for(int j = 0 ; j < k-1 ; ++j){
if(arr[j] > arr[j+1]){
swap3(arr,j,j+1);
flag = true;//用来标记这一次是否发生了交换
}
}
--k;
}
}
/**
* 冒泡排序的第三种方式:在第二种的基础上,用于处理"假如有100个数据,假如后90个都已经有序的情况"
*/
void bubblesort3(int arr[],int n){
int k;
int flag = n;
while(flag > 0){
k = flag;
flag = 0;
for(int j = 1 ; j < k ; ++j){
if(arr[j-1] > arr[j]){
swap3(arr,j-1,j);
flag = j;//对方式2的改进...用来标记发生交换的是哪一个位置
}
}
}
}
void insertsort1(int arr[], int n){
int i;
for(i = 1 ; i < n ; ++i){//当只有一个数的时候默认是有序的,所以从第二个位置上开始考虑
int j;
for(j = i-1 ; j >= 0 ; --j){//从当前位置往前找合适的位置
if(arr[j] < arr[i]){
break;
}
}
if(j != i-1){//如果找到了合适的位置...如果j=i-1,则说明[0-i]都是有序的
int temp = arr[i];//保存当前位置的数
int k;
for(k = i-1 ; k > j ; --k){//将i-1位置到j位置上的书往后移
arr[k+1] = arr[k];
}
arr[k+1] = temp;//将原来i位置上的数放到j位置后面
}
}
}
void insertsort2(int arr[],int n){
int i;
for(i = 1 ; i < n ; ++i){//从第二个位上开始扫
if(arr[i-1] > arr[i]){//如果找到一个位置,他的后面一个数要比他的前面一个数小
int j;
int temp = arr[i];//将当前位置上的数保存
for(j = i-1 ; j >= 0 && arr[j] > temp ; --j){//将i-1位置及之前的比arr[i]大的数都往后移一位
arr[j+1] = arr[j];
}
arr[j+1] = temp;//将arr[i]插入到从后面数比arr[i]小的第一个数的后面
}
}
}
/**
* 希尔排序中的插入的逻辑部分
*/
void shellinsert(int arr[],int d , int n){
int i;
for(i = d ; i < n ; ++i){//循环遍历根据步长分成的组.(步长为n，就分成了n个组)
int temp = arr[i];//保存当前位置的值
int j;
for(j = i-d ; j>= 0 && arr[j] > temp ; j -= d){//寻找合适的位置.从后往前找,找到那个比当前位置的数小的位置
arr[j+d] = arr[j];//将找到的位置后面的书都往后移
}
if(j != i-d){//如果找到了合适的位置
arr[j+d] = temp;//将当前位置的数放到合适的位置
}
}
}
/**
* 希尔排序
*/
void shellsort(int arr[],int n){
int d = n/2;//设置初始步长
while(d>=1){
shellinsert(arr,d,n);//将整个序列划分成若干个子序列,对子序列执行插入排序
d /= 2;//不断地缩小步长
}
}
/**
* 选择排序
*/
void selectsort(int arr[] , int n){
for(int i = 0 ; i < n-1 ; ++i){//扫描序列n-1次
int index = i;
for(int j = i+1 ; j < n ; ++j){//从i+1的位置开始扫
if(arr[j] < arr[index]){
index = j;//找到该次所扫描的序列的最小值
}
}
if(index != i){//如果最小数的位置发生变换
swap3(arr,i,index);//则进行交换
}
}
}
/**
* 合并有序序列
*/
void mergeArr(int arr[],int first, int mid , int last,int temp[]){
int i = first,j = mid+1;
int m = mid,n = last;
int k = 0;
while(i <= m && j <= n){//当两个序列都还有值的时候
if(arr[i] <= arr[j]){//去两个序列中的最小值
temp[k++] = arr[i++];
}else{
temp[k++] = arr[j++];
}
}
//以下两个循环用于处理某一个序列没有值的情况
while(i <= m ){
temp[k++] = arr[i++];
}
while(j <= n){
temp[k++] = arr[j++];
}
//更新原序列
for(i = 0 ; i < k ;++i){
arr[first+i] = temp[i];
}
}
/**
* 归并排序
*/
void mergeSort(int arr[],int first,int last,int temp[]){
if(first < last){//如果还没分割到只剩一个元素,就不断的分割
int mid = (first+last)/2;
mergeSort(arr,first,mid,temp);//达到左边有序的状态
mergeSort(arr,mid+1,last,temp);//达到右边有序的状态
mergeArr(arr,first,mid,last,temp);//归并
}
}
void quicksort(int arr[],int l,int r){
int i = l;
int j = r;
int x = arr[l];//将最左边的数作为基准数
if(l < r){
while(i < j){//如果i!=j就不断的进行循环
while(i < j && arr[j] >= x){//从后往前扫,找到第一个比基准数小的数
--j;
}
if(i < j){//如果找到了
arr[i++] = arr[j];//将坑填上,并将i的值++
}
while(i < j && arr[i] <= x){//从前往后扫,找到第一个比基准数大的数
++i;
}
if(i < j){
arr[j--] = arr[i];//将坑填上,并将j的值--
}
}
arr[i] = x;//将最后的基准位置上的坑填上
//分治策略
quicksort(arr,l,i-1);//递归调用
quicksort(arr,i+1,r);
}
}
void printArr(int arr[]){
int i;
for(i = 0 ; i < n ; ++i){
printf("%d " , arr[i]);
}
printf("\n");
}
void handleInput(int arr[]){
int i;
for(i = 0 ; i < n ; ++i){
scanf("%d",&arr[i]);
}
}
二、以下用这些算法来做几道简单题
在上面的基础上
nefu 30
void handleInput1(int arr[],int n){
int i;
for(i = 1 ; i < n ; ++i){
scanf("%d",&arr[i]);
}
}
int main(){
n = 10;
int arr[n];
while(scanf("%d",&arr[0])!=EOF){
handleInput1(arr,n);
shellsort(arr,n);//这里可以换成各种各样的算法
printArr(arr);
}
return 0;
}
nefu 32
#include "sort.h"
int main(){
int t;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
int arr[n];
int temp[n];
handleInput(arr);
// selectsort(arr,n);
mergeSort(arr,0,n-1,temp);
printArr(arr);
}
}