@bintou 2018-10-03T01:54:10.000000Z 字数 3122 阅读 1119

# CSI第七章查找与排序

CSI 源代码

#include <stdio.h>// A recursive binary search function. It returns location of x in// given array arr[l..r] is present, otherwise -1int binarySearch(int arr[], int l, int r, int x){   if (r >= l)   {        int mid = l + (r - l)/2;        // If the element is present at the middle itself        if (arr[mid] == x)  return mid;        // If element is smaller than mid, then it can only be present        // in left subarray        if (arr[mid] > x) return binarySearch(arr, l, mid-1, x);        // Else the element can only be present in right subarray        return binarySearch(arr, mid+1, r, x);   }   // We reach here when element is not present in array   return -1;}int ite_binarySearch(int* array, int size, int key){    int left = 0, right = size, mid = -1;    while(left <= right)    {        mid = (left + right)/2;        if(array[mid] == key)            return mid;        if(array[mid] < key)            left = mid + 1;        else             right = mid - 1;    }    return -1;}int main(void){   int arr[] = {2, 3, 4, 10, 40};   int n = sizeof(arr)/ sizeof(arr[0]);   int x = 10;   int result = binarySearch(arr, 0, n-1, x);   (result == -1)? printf("Element is not present in array")                 : printf("Element is present at index %d", result);   return 0;}

### Insertion sort

// 对大小为n的数组arr[]进行升序排序（从小到大）
insertionSort(arr, n)
for i = 1 to n-1:
Pick element arr[i] and insert it into sorted sequence arr[0…i-1]

/* Function to sort an array using insertion sort*/void insertionSort(int arr[], int n){   int i, key, j;   for (i = 1; i < n; i++)   {       key = arr[i];//当前需要插入的元素.       j = i-1;       /* Move elements of arr[0..i-1], that are          greater than key, to one position ahead          of their current position */       while (j >= 0 && arr[j] > key)       {           arr[j+1] = arr[j];           j = j-1;       }       arr[j+1] = key;   }}

### Selection Sort

void selectionSort(int arr[], int n){    int i, j, min_idx;    // One by one move boundary of unsorted subarray    for (i = 0; i < n-1; i++)    {        // Find the minimum element in unsorted array        min_idx = i;        for (j = i+1; j < n; j++)          if (arr[j] < arr[min_idx])            min_idx = j;        // Swap the found minimum element with the first element        swap(&arr[min_idx], &arr[i]);    }}

### Bubble Sort

Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order.

/* A function to implement bubble sort */void bubbleSort(int arr[], int n){   int i, j;   for (i = 0; i < n-1; i++)             // Last i elements are already in place          for (j = 0; j < n-i-1; j++)            if (arr[j] > arr[j+1])              swap(&arr[j], &arr[j+1]);}

### Quick Sort

1、选择一个主元；
2、根据主元，将数组分成两部分：比主元小的部分和比主元大的部分；
3、递归地，分别对两个部分进行Quick Sort。

/* This function takes last element as pivot, places   the pivot element at its correct position in sorted    array, and places all smaller (smaller than pivot)   to left of pivot and all greater elements to right   of pivot */int partition (int arr[], int low, int high){    int pivot = arr[high];    // pivot    int i = (low - 1);  // Index of smaller element    for (int j = low; j <= high - 1; j++)    {        // If current element is smaller than or        // equal to pivot        if (arr[j] <= pivot)        {            i++;    // increment index of smaller element            swap(&arr[i], &arr[j]);        }    }    swap(&arr[i + 1], &arr[high]);    return (i + 1);}//另一种Partitionint partition( int arr[], int low, int high) {   int pivot = arr[low], i = low, j = high + 1;   while( 1)   {    do ++i; while( arr[i] <= pivot && i <= high );    do --j; while( arr[j] > pivot );    if( i >= j ) break;        swap(&arr[i], &arr[j]);   }     swap(&arr[low], &arr[j]);   return j;}/* The main function that implements QuickSort arr[] --> Array to be sorted,  low  --> Starting index,  high  --> Ending index */void quickSort(int arr[], int low, int high){    if (low < high)    {        /* pi is partitioning index, arr[p] is now           at right place */        int pi = partition(arr, low, high);        // Separately sort elements before        // partition and after partition        quickSort(arr, low, pi - 1);        quickSort(arr, pi + 1, high);    }}

• 私有
• 公开
• 删除