我的思想随着这些闪耀的绿叶而闪耀;我的心灵因了这日光的抚触而歌唱;

排序算法总结及实现(C语言版)

C语言 致远 172℃ 0评论
#include   
#include   
using namespace std;  
  
void swap(int &a, int &b)  
{  
    int temp;  
    temp = a;  
    a = b;  
    b = temp;  
}  
  
/* 
1、选择排序 
基本思想:首先,选出最小的数放在第一位,然后选择第二小的数,放在第二位;以此类推,直到所有的数从小到大排列. 
那么,对于大小为N的数组需要N-1轮选择过程。第i轮选取第i小的数,请将其放在第i个位置上。 
不稳定  
平均时间复杂度O(N^2) 
最好情况O(N^2) 
最坏情况O(N^2) 
空间复杂度O(1) 
*/  
  
void select_sort(int a[], int n)  
{  
    for(int i = 0; i < n-1; i++){//进行n-1轮选择,也就是i的取值为【0,n-2】  
        int min_index = i;  
        //记录第i小的数所在的索引  
        for(int j = i + 1; j < n; j++){  
            if(a[j] < a[min_index])  
                min_index = j;  
        }  
        if(i != min_index){//根据记录的第i小的数的索引,找到了第i小的数。然后将该数放到其正确位置。也就是第i个位置。  
            swap(a[i] , a[min_index]);  
        }  
    }  
  
}  
  
/* 
2、冒泡排序 
基本思想: 不断比较相邻的两个数,让较大的数不断地往后移。经过一番比较,就选出了最大的数。经过第二轮比较,就选出了次大的数。以此类推。 
那么对于大小为N的数组,需要N-1轮比较。 
平均时间复杂度O(N^2) 
最好情况O(N) 
最坏情况O(N^2) 
空间复杂度O(1) 
*/  
void bubble_sort(int a[],int n)  
{  
    //要进行N-1轮比较  
    bool is_sorted = true;  
    for(int i = 0; i < n-1; i++ )//[0,n-2]恰好n-1轮比较  
    {  
        for(int j = 0; j < n-i-1 ; j++)//已经排好序的最后i个不用比较,要比较的数的个数为n-i个,那么需要比较的次数为n-i-1 { if(a[j] > a[j+1]){  
                is_sorted = false;  
                swap(a[j],a[j+1]);  
            }  
        }  
        if(is_sorted)//如果没有发生交换,说明已经排好序了,提前退出循环,所以最好情况下时间复杂度为O(N)  
            break;  
    }  
}  
/* 
3、快速排序 
基本思想:采用分而治之的思想,将要排序的数分成左右两部分,其中一部分的数据比key小,另一部分数据比key大。然后将所分得的两部分数据进行同样的划分。重复执行以上的划分操作。 
平均时间复杂度O(Nlog2(N)) 
最好情况O(Nlog2(N)) 
最坏情况O(N^2) 
空间复杂度O(Nlog2(N)) 
*/  
int partition(int arr[], int low, int high)//返回划分的中间值  
{  
    int key;  
    key = arr[low];//相当于在索引low处挖坑,下一个就要找合适的数据来填坑  
      
    while(low < high)  
    {  
        while(low < high && arr[high] >= key){  
            high --;  
        }  
        if(low < high)  
            arr[low ++] = arr[high];//找到合适的数据填到了low坑,但是形成了high坑,继续找合适的数据  
          
        while( low < high && arr[low] <= key)  
            low ++;  
        if( low < high)  
            arr[high --] =  arr[low];//low又成了坑  
    }  
  
    arr[low] = key;//将key填到这个坑  
    return low;  
}  
void quick_sort(int num[], int low, int high)  
{  
    int pos;  
    if(low < high){  
        pos = partition(num, low, high);  
        quick_sort(num, low, pos-1);  
        quick_sort(num, pos+1, high);  
    }  
}  
/*快速排序非递归版*/  
void quicksort2(int num[], int low, int high)  
{  
    int key = num[low];  
    stack s;  
    if(low < high){ int pos = partition(num, low, high); if(pos-1 > low){  
            s.push(pos - 1);  
            s.push(low);  
        }  
        if(pos+1 < high){ s.push(high); s.push(pos + 1); } while(!s.empty()){ int l = s.top(); s.pop(); int r = s.top(); s.pop(); pos = partition(num, l, r); if(pos - 1 > l){  
                s.push(pos - 1);  
                s.push(l);  
            }  
            if(pos + 1 < r){  
                s.push(r);  
                s.push(pos + 1);  
            }  
        }  
    }  
}  
/* 
4、插入排序 
基本思想:将元素逐个添加到已经排好序的数组中去。 
平均时间复杂度O(n^2) 
最好时间复杂度O(n) 
最坏时间复杂度O(n^2) 
空间复杂度O(1) 
*/  
void insert_sort(int a[], int n)  
{  
    //要进行n-1趟插入  
    for(int i = 1; i < n; i++){//假设第0个已在正确位置,从第一个开始插入  
        //第i趟插入需要在【0,i-1】中找到i的合适位置  
        int j = 0;  
        while( (j < i) && (a[i] > a[j]) ){  
            j ++;  
        }  
        //如果找到合适位置i应该!=j,如果i==j,说明i正好在正确的位置  
        if( i != j){  
            //将a[i]插入到合适的位置,即位置j,那么[j, i-1]位置上的数应该后移。先保存a[i],然后后移。  
            int tmp = a[i]; //空间复杂度O(1)  
            for(int k = i; k > j; k--)  
                a[k] = a[k-1];    
            a[j] = tmp;       
        }  
    }  
  
}  
/* 
5、希尔排序 
基本思想:将无序数组分成若干个子序列,子序列不是逐段分割的,而是相隔特定增量。对各个子序列进行插入排序。 
然后再选择一个更小的增量,再将数组分割成多个子序列进行排序。最后选择增量为1,即使用直接插入排序,使最终数组成为有序数组。 
平均时间复杂度O(n^1.3) 
最好时间复杂度O(n) 
最坏时间复杂度O(n^2) 
空间复杂度O(1) 
*/  
void shell_sort(int a[], int n)  
{  
    int gap;  
    for( gap = n/2; gap > 0; gap /= 2){  
        for(int i = gap; i < n; i ++){ for(int j = i - gap; j >= 0 && a[j] < a[j + gap]; j-=gap){//每个元素与自己组内的元素进行插入排序  
                swap(a[j], a[j + gap]);  
            }  
        }  
    }  
}  
  
/* 
6、归并排序: 
基本思想:将待排序序列【0,n-1】看成是n个长度为1的有序序列,将相邻的有序表成对归并,得到n/2个长度为2的有序表。再次归并,得到n/4个长度为4的有序表。 
依次类推,最后得到长度为n的1个有序表。 
所以归并排序其实要做两件事: 
1、先递归的分解数列, 
2、再合并数列就完成了归并排序。 
 
先来考虑如何合并? 
每次合并过程中都要对两个有序的序列段进行合并,然后排序 
待合并的两个有序序列段分别为 R[low, mid] 和 R[mid+1, high] 
先将它们合并到一个暂存数组R2,合并完再将R2复制回R1中。 
这样一次合并排序就完成了。 
 
最好、最坏和平均时间复杂度都是O(nlogn), 
空间复杂度是O(n) 
*/  
void merge(int a[], int low ,int mid, int high,int tmp[])  
{  
    int i,j,k;  
    i = low;  
    j = mid + 1;  
    k = 0;//k是存放临时合并数组的下表  
  
    while( i <= mid && j <= high){  
        if( a[i] < a[j])  
            tmp[k++] = a[i++];  
        else   
            tmp[k++] = a[j++];  
    }  
  
    while( i <= mid)  
        tmp[k++] = a[i++];  
    while( j <= high)  
        tmp[k++] = a[i++];  
  
    //最后再复制回a  
    for(i = 0; i < k; i++ )  
        a[low+i] = tmp[i];//!!!!此处a是从low开始,tmp是从0开始。  
}  
void merge_sort(int a[],int low, int high, int tmp[])  
{  
    if(low < high){  
        int mid = (low + high)/2;  
        merge_sort(a,low, mid, tmp);  
        merge_sort(a, mid+1, high, tmp);  
        merge(a, low, mid, high, tmp);  
    }  
}  
  
bool sort(int a[], int n)  
{  
    int *p = new int[n];  
    if(p == NULL) return false;  
    merge_sort(a, 0, n-1, p);  
    delete []p;  
    return true;  
}  
/* 
堆排序 
 
*/  
int main()  
{  
    int num[] = {1 , 7, 7 ,8 ,0,3,5};  
    //select_sort(num, 7);  
    //bubble_sort(num,7);  
    //quick_sort(num,0,6);  
    quicksort2(num, 0, 6);  
    //insert_sort(num,7);  
    //shell_sort(num,7);  
    //sort(num,7);  
    for(int i = 0; i < 7; i++){  
        cout << num[i]  << endl;  
    }  
    return 0;  
}  

转载请注明:致远博客 » 排序算法总结及实现(C语言版)

喜欢 (0)
发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址