#排序算法#【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;
        }

    }
}