分类 Algorithms 下的文章

Heap Sort 堆排序C语言实现

#Heap Sort-堆排序

此贴由戴维营教育学员翻译,鄙人整理,特意为戴维营教育零基础学员课外学习之用.

##堆排序 :
堆排序就是使用堆来对数组进行排序。而堆数据结构,可以被看作是一个完整的,平衡二叉树的数组对象。堆分大根堆和小根堆,小根堆(大根推)都有个属性:除了根以外的每一个节点,其值至少(至多)是该节点的父节点的值。由这个性质可知大根堆的堆顶的值肯定是所有值中最大的,小根堆的堆顶的值是所有值中最小的,因此,堆中最小的(最大的)元素被存储在根节点,而且一个节点的子树包含一些比自己较大的(较小的)节点。

##算法:
它通过插入由用户输入的元素到对应位置来构建一个堆:
1,增加堆的大小用存储插入的值.
2,将输入值插在最后的地方.
3,将插入值与其父节点的值比较,直到满足堆属性,然后将其放置在其正确位置.

1, heap[1]是最小的元素,因此,我们删除heap[1],堆的大小减小。
2,现在heap[1]必须用新值来填补,我们把最后一个元素放这地方,看看它是否适合;如果不适合,采取两子节点中的最小元素替代父节点。
3,再看看最后一个元素在那个地方是否适合。

##特性:
最好情况下执行 - 当输入数组早已排序好, 时间复杂度: O(nlogn)
最坏情况下执行 - 当输入数组是倒序, 时间复杂度: O(nlogn);
平均情况下执行 - 时间复杂度: O(nlogn);
它不需要一个额外的空间来排序,因此空间复杂度是: O(1)
它是不稳定的排序算法;

##堆排序C语言实现

#include <stdio.h>
#include <limits.h>
/*Declaring heap globally so that we do not need to pass it as an argument every time*/

/* Heap used here is Min Heap */
int heap[1000000],heapSize;

/*Initialize Heap*/
void Init()
{
        heapSize = 0;
        heap[0] = -INT_MAX;
}

/*Insert an element into the heap */
void Insert(int element)
{
        heapSize++;
        heap[heapSize] = element; /*Insert in the last place*/
        /*Adjust its position*/
        int now = heapSize;
        while(heap[now/2] > element)
        {
                heap[now] = heap[now/2];
                now /= 2;
        }
        heap[now] = element;
}

int DeleteMin()
{
        /* heap[1] is the minimum element. So we remove heap[1]. Size of the heap is decreased.Now heap[1] has to be filled. We put the last element in its place and see if it fits.If it does not fit, take minimum element among both its children and replaces parent with it.Again See if the last element fits in that place.*/
        int minElement,lastElement,child,now;
        minElement = heap[1];
        lastElement = heap[heapSize--];
        /* now refers to the index at which we are now */
        for(now = 1; now*2 <= heapSize ;now = child)
        {
                /* child is the index of the element which is minimum among both the children */
                /* Indexes of children are i*2 and i*2 + 1*/
                child = now*2;
                /*child!=heapSize beacuse heap[heapSize+1] does not exist, which means it has only one child */
                if(child != heapSize && heap[child+1] < heap[child] )
                {
                        child++;
                }
                /* To check if the last element fits ot not it suffices to check if the last element is less than the minimum element among both the children*/
                if(lastElement > heap[child])
                {
                        heap[now] = heap[child];
                }
                else /* It fits there */
                {
                        break;
                }
        }
        heap[now] = lastElement;
        return minElement;
}

int main(void)
{
        int number_of_elements;
        scanf("%d",&number_of_elements);
        int iter, element;
        Init();
        for(iter = 0;iter < number_of_elements;iter++)
        {
                scanf("%d",&element);
                Insert(element);
        }
        for(iter = 0;iter < number_of_elements;iter++)
        {
                printf("%d ",DeleteMin());
        }
        printf("\n");
        return 0;
}

Merge Sort 归并排序C语言实现

#Merge Sort-归并排序

此贴由戴维营教育学员翻译,鄙人整理,特意为戴维营教育零基础学员课外学习之用.

归并排序是基于分而治之的方法,它把这个要进行排序的列表,平分成两半,变成两个未排序的列表。再对这两个无序列表进行同样的排序,合并,最终得到一个排好序的列表。这两个无序列表是通过不断地调用归并排序算法进行排序;我们最终得到一个大小为1的已经排好序的列表。这两个大小为1的列表,然后又合并。

##算法:

这是一种分而治之的算法。工作原理如下 -

  • 1,把我们输入的需要排序的列表从中间分成两半,称为左半部分和右半部分。
    例如:假设输入是-10 32 45 -78 91 1 0 -16,则左部分是-10 32 45 -78,右部分将是91 1 0 6。
  • 2,把这左右两部分分别单独排序。需要注意的是,这里的排序并不意味着使用其他一些方法来排序。而是我们递归地使用一样的函数。
  • 3,然后合并这两个排好序的列表。

输入元素的总个数:number_of_elements, 然后输入这么多个元素保存到数组array[number_of_elements]里面。接下来调用函数 MergeSort() 对这个数组进行排序。
MergeSort()函数对数组[left,right]范围内的元素排序,即从索引left到索引right之的所有元素。
Merge() 函数的作用是合并两个已排好序的部分。排好序的部分是从[left,mid][mid+1,right]。合并后输出这个排好序的数组。

MergeSort() 函数:

它把数组,以及该数组的最左边和最右边的索引作为它的参数。数组的中间元素通过公式(left + right)/2计算得出。检查是否(left<right)因为只有(left<right)时我们才需要排序,而当left=right时表示它已经排好序了。排序左半部分通过调用MergeSort(array,left,mid),排序右半部分通过调用MergeSort(array,mid + 1, right),最后调用Merge() 函数把这两个数组合并到一起。

最后复制回已排序的数组到原数组。

##特性:

  • 最好的情况 - 当数组已经排序时, 时间复杂度为O(nlogn)
  • 最坏的情况 - 当数组是按相反的顺序时, 时间复杂度为O(nlogn)
  • 一般情况下 - 时间复杂度为O(nlogn)
  • 额外的空间是必需的,所以数组归并排序空间复杂度是O(n) ,链表归并排序的空间复杂度是O(logn).

##归并排序C语言实现


#include <stdio.h>
/*This is called Forward declaration of function */
void Merge(int * , int , int , int );
/* Logic: This is divide and conquer algorithm. This works as follows.
         (1) Divide the input which we have to sort into two parts in the middle. Call it the left part and right part.
             Example: Say the input is  -10 32 45 -78 91 1 0 -16 then the left part will be -10 32 45 -78 and the right part will be  91 1 0 6.
         (2) Sort Each of them seperately. Note that here sort does not mean to sort it using some other method. We already wrote fucntion to sort it. Use the same.
         (3) Then merge the two sorted parts.
*/

/*This function Sorts the array in the range [left,right].That is from index left to index right inclusive
 */
 
void MergeSort(int *array, int left, int right)
{
        int mid = (left+right)/2;
        /* We have to sort only when left<right because when left=right it is anyhow sorted*/
        if(left<right)
        {
                /* Sort the left part */
                MergeSort(array,left,mid);
                /* Sort the right part */
                MergeSort(array,mid+1,right);
                /* Merge the two sorted parts */
                Merge(array,left,mid,right);
        }
}


/* Merge functions merges the two sorted parts. Sorted parts will be from [left, mid] and [mid+1, right].
 */
void Merge(int *array, int left, int mid, int right)
{
        /*We need a Temporary array to store the new sorted part*/
        int tempArray[right-left+1];
        int pos=0,lpos = left,rpos = mid + 1;
        while(lpos <= mid && rpos <= right)
        {
                if(array[lpos] < array[rpos])
                {
                        tempArray[pos++] = array[lpos++];
                }
                else
                {
                        tempArray[pos++] = array[rpos++];
                }
        }
        while(lpos <= mid)  tempArray[pos++] = array[lpos++];
        while(rpos <= right)tempArray[pos++] = array[rpos++];
        int iter;
        /* Copy back the sorted array to the original array */
        for(iter = 0;iter < pos; iter++)
        {
                array[iter+left] = tempArray[iter];
        }
        return;
}


int main(void)
{
        int number_of_elements;
        scanf("%d",&number_of_elements);
        int array[number_of_elements]; 
        int iter;
        for(iter = 0;iter < number_of_elements;iter++)
        {
                scanf("%d",&array[iter]);
        }
        /* Calling this functions sorts the array */
        MergeSort(array,0,number_of_elements-1); 
        for(iter = 0;iter < number_of_elements;iter++)
        {
                printf("%d ",array[iter]);
        }
        printf("\n");
        return 0;
}

Quick Sort 快速排序C语言实现

#Quick Sort-快速排序

此贴由戴维营教育学员翻译,鄙人整理,特意为戴维营教育零基础学员课外学习之用.

快速排序像归并排序一样是一个分而治之的算法,但它不想归并排序那样,它不需要额外的空间,在待排序的集合内就地排序。

这个分割步骤就是选择一个基准点把数组分割,小于或等于基准点的元素全排到左边去,大于或等于基准点的元素全部排到基准点右边去。再依次对左右两边的元素递归地进行快速排序。

##算法
该算法的关键在于分区.

  • 从数列中挑出一个元素,称为 "基准"(pivot),
  • 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
  • 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。虽然一直递归下去,但是这个算法总会退出,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。

基准选择与分区:

快速排序图示:

##特性

  • 最佳性能:当分区产生两个区域的大小是n/2时(n是列表中的元素的总数),时间复杂度为O(nlgn).
  • 最差性能:当分区产生一个区域的大小是n - 1时(n是列表中的元素的总数),另一个区域大小为1,时间复杂度为O(n2).
  • 平均情况:时间复杂度O(n(lgn))
  • 在最坏的情况下,使用O(lg(n))额外的空间, 这是一个不稳定的算法。

##快速排序-C语言代码

#include <stdio.h>
/* Logic:
This is divide and conquer algorithm like Merge Sort.
Unlike Merge Sort this does not require extra space.So it sorts in place.
Here dividing step is chose a pivot and parition the array such that all elements less than or equal to pivot are to the left of it andd all the elements which are greater than or equal to the pivot are to the right of it.
Recursivley sort the left and right parts.
*/

void QuickSort(int *array, int from, int to)
{
        if(from>=to)return;
        int pivot = array[from]; /*Pivot I am chosing is the starting element */
        /*Here i and j are such that in the array all elemnts a[from+1...i] are less than pivot, all elements a[i+1...j] are greater than pivot and the elements a[j+1...to] are which we have not seen which is like shown below.
          ________________________i_________________j___________
          |pivot|....<=pivot......|....>=pivot......|.........|
          If the new element we encounter than >=pivot the above variant is still satisfied.
          If it is less than pivot we swap a[j] with a[i+1].
         */
        int i = from, j, temp;
        for(j = from + 1;j <= to;j++)
        {
                if(array[j] < pivot) 
                {
                        i = i + 1;
                        temp = array[i];
                        array[i] = array[j];
                        array[j] = temp;
                }
        }
        /* Finally The picture is like shown below
          _______________________i____________________
          |pivot|....<=pivot......|....>=pivot......|
        */
        temp = array[i];
        array[i] = array[from];
        array[from] = temp;
        /* So we the array is now 
          ____________________i______________________
          |...<=pivot......|pivot|....>=pivot......|
        */
        /*Recursively sort the two sub arrays */
        QuickSort(array,from,i-1);
        QuickSort(array,i+1,to);
}
int main()
{
        int number_of_elements;
        scanf("%d",&number_of_elements);
        int array[number_of_elements]; 
        int iter;
        for(iter = 0;iter < number_of_elements;iter++)
        {
                scanf("%d",&array[iter]);
        }
        /* Calling this functions sorts the array */
        QuickSort(array,0,number_of_elements-1); 
        for(iter = 0;iter < number_of_elements;iter++)
        {
                printf("%d ",array[iter]);
        }
        printf("\n");
        return 0;
}

Insertion Sort插入排序C语言实现

#Insertion Sort-插入排序

此贴由戴维营教育学员翻译,鄙人整理,特意为戴维营教育零基础学员课外学习之用.

##介绍
插入排序使用线性搜索来查找未排序的列表中第一个元素,其在已经排好序的那部分列表的插入位置。是一个基本排序算法,多用于排序较小的数据集或插入一个新元素到前面已排序好的列表中。

##算法:

插入排序从第1个元素开始,可以认为这个元素已经排序,然后把后面的元素依次插入前面有序列表中。

  • 1,假设如果数组排序到i位置,我们可以对数组进行排序,直到从第(i+1)个元素到数组最后一个元素正确插入到当前元素的前面。

  • 2,第i+1个元素的插入位置必须在遍历第个元素到第i个元素之间找到。

  • 3,任何数组排序到第个位置(单个元素总是排序),这样就知道如何扩大,怎么对整个数组排序。

##特性:

  • 最佳性能的情况——当数组已经排序:O(n), 总的比较次数:N-1,总的交换次数:N-1

  • 最差性能的情况——当数组排序以相反的顺序: O(n2), n-1次比较和交换的遍历。

  • 平均性能情况: O(n2)

  • 排序过程中的比较次数和交换次数严重依赖于数据的输入.

  • 它排序过程中不需要任何额外的空间,因此空间复杂度是 O(1)

##插入排序-C语言代码

#include <stdio.h>
/* Logic :
Suppose if the array is sorted till index i then we can sort the arry till i+1 by inserting i+1 th element in the correct position from 0 to i+1.
The position at which (i+1)th element has to be inserted has to be found by iterating from 0 to i.
As any array is sorted till 0th postion(Single element is always sorted) and we know how to expand, we can sort the whole array.
 */
void InsertionSort(int *array , int number_of_elements)
{
        int iter,jter;
        for(iter=1;iter<number_of_elements;iter++)
        {
                int current_element = array[iter];
                jter = iter-1;
                while(jter>=0 && array[jter] > current_element)
                {
                        array[jter+1] = array[jter];
                        jter--;
                }
                array[jter+1] = current_element;
        }
}

int main(void)
{
        int number_of_elements;
        scanf("%d",&number_of_elements);
        int array[number_of_elements];
        int iter;
        for(iter = 0;iter < number_of_elements;iter++)
        {
                scanf("%d",&array[iter]);
        }
        /* Calling this functions sorts the array */
        InsertionSort(array,number_of_elements);
        for(iter = 0;iter < number_of_elements;iter++)
        {
                printf("%d ",array[iter]);
        }
        printf("\n");
        return 0;
}

Bubble Sort冒泡排序C语言实现

#Bubble Sort

此贴特意为戴维营教育零基础学员课外学习之用.

这是一种排序算法,他就是相邻的两个元素两两比较,如果顺序不对就互相交换位置,比较一直往后重复,直到不需要交换为止,也就是已经排好序. 那个比较小的元素"像气泡一样往上冒泡"到最顶端,因此而得名冒泡排序.

###算法

从待排列表的第一个元素开始,一直比较和交换相邻的两个元素直到列表被排好序

  • 比较相邻的两个元素,并检查他们是否是正确的序号(第二个应该比第一个要大).
  • 如果他们的顺序不正确,那么交换他们的位置,使其第二个比第一个大.

让一个整型变量int iter;来表示循环的次数,那么iter的取值范围就是从1到n-1这样一个整型区间,n是待排序列表的元素的个数.
判断

  1. 如果在循环变量iter的位置,第二个元素的值小于第一个元素的值(iter-1位置),那么就交换他们的位置.
  2. 否则,比较的位置移动到下一个元素的地方:iter+1的位置.
    这样,待排序列表的有效大小就会在每次遍历中把最大的元素移动到有序子列表里最终的位置后减少一. 一直重复上面2个步骤知道列表被全部排好序,不需要任何元素交换. 如:有效大小缩减至1.

###特性

  1. 最佳性能:当列表是有序的,那么我们只需遍历一下.因此时间复杂度是 O(n).
  2. 最差性能:当列表是倒序的,那么我们需要遍历N次,每次要N次比较和交换,因此时间复杂度是 O(n2)
  3. 平均性能:时间复杂度是: O(n2)
  4. 这个不需要任意额外的临时变量空间,因此空间复杂度是 O(1)

###冒泡排序-C语言代码

#include <stdio.h>

/*
Logic steps : Do the following thing until the list is sorted
(i) Compare two adjacent elements and check if they are in correct order(that is second one has to be greater than the first).
(ii) Swap them if they are not in correct order.
 */

void BubbleSort(int *array,int number_of_elements)
{
        int iter, temp, swapped;
        do
        {
                swapped = 0; /* If no element is swapped array is sorted */
                /* In the following loop compare every pair of adjacent elements and check if they are in correct order */
                for(iter = 1; iter < number_of_elements; iter++)
                {
                        if(array[iter-1] > array[iter])
                        {
                                temp = array[iter-1];
                                array[iter-1] = array[iter];
                                array[iter] = temp;
                                swapped = 1;
                        }
                }

        }while(swapped);
}
int main(void)
{
        int number_of_elements;
        scanf("%d",&number_of_elements);
        int array[number_of_elements]; 
        int iter;
        for(iter = 0;iter < number_of_elements;iter++)
        {
                scanf("%d",&array[iter]);
        }
        /* Calling this functions sorts the array */
        BubbleSort(array,number_of_elements); 
        for(iter = 0;iter < number_of_elements;iter++)
        {
                printf("%d ",array[iter]);
        }
        printf("\n");
        return 0;

}