CSI第七章查找与排序

CSI 源代码

Binary Search

#include <stdio.h>
// A recursive binary search function. It returns location of x in
// given array arr[l..r] is present, otherwise -1
int 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);
}
//另一种Partition
int 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);
    }
}

参考资料