乐趣区

关于c:排序算法

jiezi

前沿

明天咱们来看看几种常见的排序算法

插入排序

定义

插入排序的算法形容是一种简略直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应地位并插入。

形容

  • 从第一个元素开始，该元素能够认为曾经被排序
  • 取出下一个元素，在曾经排序的元素序列中从后向前扫描
  • 如果该元素（已排序）大于新元素，将该元素移到下一地位
  • 反复步骤 3，直到找到已排序的元素小于或者等于新元素的地位
  • 将新元素插入到该地位后
  • 反复步骤 2～5

复杂度

工夫复杂度 O(N^2)

空间复杂度 O(1)

复法 

void InsertionSort(int *arr, int size)    
{    
    int i, j, tmp;    
    for (i = 1; i < size; i++) {if (arr[i] < arr[i-1]) {// 如果要大在前 改这个判断 和 arr[j] < temp   
            tmp = arr[i];    
            for (j = i - 1; j >= 0 && arr[j] > tmp; j--) {arr[j+1] = arr[j];    
            }  
            arr[j+1] = tmp;    
        }          
    }    
}

冒泡排序

形容

比拟相邻的元素。如果第一个比第二个大，就替换它们两个

复杂度

工夫复杂度 O(n^2)

空间复杂度 O(1)

算法 

void BubbleSort(int *arr, int size)  
{  
    int i, j, tmp;  
    for (i = 0; i < size - 1; i++) {for (j = 0; j < size - i - 1; j++) {if (arr[j] > arr[j+1]) {tmp = arr[j];  
                arr[j] = arr[j+1];  
                arr[j+1] = tmp;  
            }  
        }  
    }  
}

抉择排序

定义

抉择排序，是一种简略直观的排序算法。它的工作原理：首先在末排序列中找到最小（大）元素，寄存到排序序列的起始地位，直到全副待排序的数据元素排完。

复杂度

工夫复杂度为 O(n^2)

空间复杂度为 O(1)

算法 

void SelectionSort(int *arr, int size)
{
    int i,j,temp,k;
    for (i = 0; i < size-1; i++) {
        k = i;
        for (j = i+1; j < size; j++) {if (arr[j] > arr[k]) {k = j;}
        }
        temp = arr[k];
        arr[k] = arr[i];
        arr[i] = temp;
    }
}

致谢

感激你看完这篇文章，有什么不对的中央欢送指出，谢谢????

退出移动版