简单了解C语言中直接插入排序与直接选择排序实现

直接插入排序
基本思路：
1. 从a[0]开始，也就是从1个元素开始是有序的，a[1]~a[n-1]是无序的。
2. 从a[1]开始并入前面有序的数组，直到n-1。

#include <stdio.h>
#define N 5 

void insertsort(int a[], int n);
void swap(int *x, int *y); 

void insertsort(int a[], int n){
  int i,j;
  for(i=1; i<n; i++){
    for(j=i; j>0 && a[j]<a[j-1]; j--){
      swap(&a[j], &a[j-1]);
    }
  }
} 

void swap(int *x, int *y){
  int i = *x;
  *x = *y;
  *y = i;
} 

int main(void){
  int a[N] = {2, 5, 3, 1, 8};
  insertsort(a, N);
  int i;
  for(i=0; i<N; i++)
    printf("%d ", a[i]);
  return 0;
}

直接选择排序

基本思路：
1. 从1开始通过对比找出最小的数的下标。然后把这个下标的值和0交换。
2. 循环把值交换到1 2 3 ... n-1。

#include <stdio.h>
#define N 5 

void selectsort(int a[], int n);
void swap(int *x, int *y); 

void selectsort(int a[], int n){
  int i,j;
  for(i=0; i<n; i++){
    int min = i;
    for(j=i+1; j<n; j++){
      if(a[j] < a[min]){
        min = j;
      }
    }
    swap(&a[i], &a[min]);
  }
} 

void swap(int *x, int *y){
  int i = *x;
  *x = *y;
  *y = i;
} 

int main(void){
  int a[N] = {2, 5, 3, 1, 8};
  selectsort(a, N);
  int i;
  for(i=0; i<N; i++)
    printf("%d ", a[i]);
  return 0;
}
赞 (0)

相关推荐

  • c语言实现冒泡排序、希尔排序等多种算法示例

    实现以下排序 插入排序O(n^2) 冒泡排序 O(n^2) 选择排序 O(n^2) 快速排序 O(n log n) 堆排序 O(n log n) 归并排序 O(n log n) 希尔排序 O(n^1.25) 1.插入排序 O(n^2) 一般来说,插入排序都采用in-place在数组上实现.具体算法描述如下:⒈ 从第一个元素开始,该元素可以认为已经被排序⒉ 取出下一个元素,在已经排序的元素序列中从后向前扫描⒊ 如果该元素(已排序)大于新元素,将该元素移到下一位置⒋ 重复步骤3,直到找到已排序的元素

  • C语言实现排序算法之归并排序详解

    排序算法中的归并排序(Merge Sort)是利用"归并"技术来进行排序.归并是指将若干个已排序的子文件合并成一个有序的文件. 一.实现原理: 1.算法基本思路 设两个有序的子文件(相当于输入堆)放在同一向量中相邻的位置上:R[low..m],R[m+1..high],先将它们合并到一个局部的暂存向量R1(相当于输出堆)中,待合并完成后将R1复制回R[low..high]中. (1)合并过程 合并过程中,设置i,j和p三个指针,其初值分别指向这三个记录区的起始位置.合并时依次比较R[i

  • C语言 奇偶排序算法详解及实例代码

    C语言 奇偶排序算法详解及实例代码

    C语言奇偶排序算法 奇偶排序,或奇偶换位排序,或砖排序,是一种相对简单的排序算法,最初发明用于有本地互连的并行计算.这是与冒泡排序特点类似的一种比较排序.该算法中,通过比较数组中相邻的(奇-偶)位置数字对,如果该奇偶对是错误的顺序(第一个大于第二个),则交换.下一步重复该操作,但针对所有的(偶-奇)位置数字对.如此交替进行下去. 使用奇偶排序法对一列随机数字进行排序的过程 处理器数组的排序 在并行计算排序中,每个处理器对应处理一个值,并仅有与左右邻居的本地互连.所有处理器可同时与邻居进行比较.交

  • C语言实现基于最大堆和最小堆的堆排序算法示例

    堆定义 堆实际上是一棵完全二叉树,其任何一非叶节点满足性质: Key[i]<=key[2i+1]&&Key[i]<=key[2i+2](小顶堆)或者:Key[i]>=Key[2i+1]&&key>=key[2i+2](大顶堆) 即任何一非叶节点的关键字不大于或者不小于其左右孩子节点的关键字. 堆排序的思想 利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性,使得每次从无序中选择最大记录(最小记录)变得简单. 最大堆:所有节点的子节点比其

  • C语言基本排序算法之插入排序与直接选择排序实现方法

    本文实例讲述了C语言基本排序算法之插入排序与直接选择排序实现方法.分享给大家供大家参考,具体如下: 声明待排序元素类型 /*-------------------------- typedef.h 方便修改待排序元素类型 -------------------------------------*/ #ifndef TYPEDEF_H #define TYPEDEF_H typedef int T; #endif 插入排序: /*---------------------------------

  • 希尔排序算法的C语言实现示例

    希尔排序算法的C语言实现示例

    希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本.希尔排序是非稳定排序算法. 希尔排序是基于插入排序的以下两点性质而提出改进方法的: 插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率 但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位 希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能.这样可以让一个元素可以一次性地朝最终位置前进一大步.然后算法再取越来越小的步长进行排序,算法的最后一步就是普通的插入排序,但是到了这步,需排序的数据几

  • c语言快速排序算法示例代码分享

    步骤为:1.从数列中挑出一个元素,称为 "基准"(pivot);2.重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边).在这个分区退出之后,该基准就处于数列的中间位置.这个称为分区(partition)操作.3.递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序.递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了.虽然一直递归下去,但是这个算法总会退出,因为在每次的迭代(iterat

  • C语言演示对归并排序算法的优化实现

    基础 如果有两个数组已经有序,那么可以把这两个数组归并为更大的一个有序数组.归并排序便是建立在这一基础上.要将一个数组排序,可以将它划分为两个子数组分别排序,然后将结果归并,使得整体有序.子数组的排序同样采用这样的方法排序,这个过程是递归的. 下面是示例代码: #include "timsort.h" #include <stdlib.h> #include <string.h> // 将两个长度分别为l1, l2的已排序数组p1, p2合并为一个 // 已排序

  • C语言中使用快速排序算法对元素排序的实例详解

    C语言中使用快速排序算法对元素排序的实例详解

    调用C语言的快速排序算法qsort(); #include<stdio.h> #include<stdlib.h> #include<string.h> #define SIZE 100 //从小到大排序 int comp1(const void *x,const void *y) { return *(int *)x - *(int *)y; } //从大到小排序 int comp2(const void *x,const void *y) { return *(in

  • C语言实现选择排序、直接插入排序、冒泡排序的示例

    选择排序 选择排序是一种简单直观的排序算法,其核心思想是:遍历数组,从未排序的序列中找到最小元素,将其放到已排序序列的末尾. 时间复杂度:O(n^2) 稳定性 :不稳定 /* * @brief selection sort */ void selection_sort(int a[], int n) { int i, j, min, tmp; for (i = 0; i < n - 1; ++i) { min = i; for (j = i+1; j < n; ++j) { if (a[j]

  • C语言中快速排序和插入排序优化的实现

    C语言中快速排序和插入排序优化的实现

    快速排序 快速排序思想 1962年,由C.A.R.Hoare创造出来.该算法核心思想就一句话:"排序数组时,将数组分成两个小部分,然后对它们递归排序".然而采取什么样的策略将数组分成两个部分是关键,想想看,如果随便将数组A分成A1和A2两个小部分,即便分别将A1和A2排好序,那么A1和A2重新组合成A时仍然是无序的.所以,我们可以在数组中找一个值,称为key值,我们在把数组A分解为A1和A2前先对A做一些处理,让小于key值的元素都移到其左边,所有大于key值的元素都移到其右边.这样递

  • c语言实现奇偶排序算法

    =====第2题:奇偶排序(一)===== 总时间限制:1000ms内存限制:65536kB描述输入十个整数,将十个整数按升序排列输出,并且奇数在前,偶数在后.输入输入十个整数输出按照奇偶排序好的十个整数 复制代码 代码如下: #include<stdio.h> #define  COUNT 10#define bool int#define true 1#define false 0 /*****负责冒泡排序***/int* sortFunction(int data[]){ int i,j

随机推荐