首页 > 代码库 > #排序算法#【1】概述、冒泡排序、选择排序

#排序算法#【1】概述、冒泡排序、选择排序

排序算法分类:

  1. 内部排序(在排序过程中不需要访问外存就可以完成排序)
  2. 外部排序
内部排序分类:
  1. 交换排序
    • 冒泡排序
    • 快速排序
  2. 选择排序
    • 直接选择排序
    • 堆排序
  3. 插入排序
    • 直接插入排序
    • 希尔排序
  4. 合并排序
外部排序:
     常见的是多路归并算法,即将原文件分为多个能够一次装入内存一部分,分别把每一部分调入内存完成排序,然后对已经排序的子文件进行归并排序
 
 
冒泡排序法:

  冒泡排序法是一种相邻数据交换的排序方法。
  冒泡排序法的基本思想是:对待排序记录关键字从后往前(逆序)进行多遍扫描,当发现相邻两个关键字的次序与排序要求的规则不符时,就将这两个记录进行交换。这样,关键字较小的记录将逐渐从后面向前面移动,就象气泡在水中向上浮一样,所以该算法也称为气泡排序法。
     
  核心代码如下:
//冒泡排序
//a  传递的要排序的数组
//n  数组元素的长度
void BubbleSort(int a[],int n){
    int i,j,temp;
    int flag = 0;
    for(i = 0 ; i < n ; i++){
        for(j = n - 1 ; j > i; j--){
            if(a[j] < a[j-1]){
                temp = a[j-1];
                a[j-1] = a[j];
                a[j] = temp;
                flag = 1;
            }
        }
        
       //如果一遍下来没有数据交换,则不需要再继续循环
        if(flag == 0)
            break;
        else
            flag = 0;
    }
}

 

 
简单选择排序法

  选择排序的基本思想:对n个记录进行扫描,选择最小的记录,将其输出,接着在剩下的n-1个记录中扫描,选择最小的记录将其输出,不断重复这个过程,直到只剩一个记录为止。
 
  
 
  核心代码如下:
//简单选择排序
//a  要排序的数组
//n  数组的元素个数
void SelectSort(int a[],int n){
    int i,j,k,;
    int temp;

    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){
            temp = a[i];
            a[i] = a[k];
            a[k] = temp;
        }

    }
}